MathB.in - Share Mathematics with LaTeX and Markdown

###Statement

Calculate following:

$$
\lim_{n\to\infty}\prod_{k=1}^{n-1}\frac{n^2+k}{n^2}
$$

### Solution
First, rearrange a bit:

$$
\lim_{n\to\infty}\prod_{k=1}^{n-1}\frac{n^2+k}{n^2}=\lim_{n\to\infty}\prod_{k=1}^{n-1}\left(1+\frac{k}{n^2}\right)
$$

Now, introduce family of functions:
$$
f_n(x) = \prod_{k=1}^{n-1}\left(1+\frac{kx}{n^2}\right)
$$

So we need to find:
$$
\lim_{n\to\infty}f_n(1)
$$

Lets now find coefficient of $f_n(x)$ at term $x$. It's all possible ways to pick exactly one with x. I'll denote $a_k$ as coefficient at $x^k$. Hence:

$$
\begin{align}
a_0 &= 1 \\
a_1 &= (1 + 2 + ... + (n-1))\frac{1}{n^2} = \frac{n(n-1)}{2}\frac{1}{n^2} = \frac{(n-1)}{2n}
\end{align}
$$

Next goes $a_2$ and things go wild:

$$
\begin{align}
a_2 =& \frac{1}{n^4} (1\cdot 2+1\cdot 3+1\cdot 4+...1\cdot (n-1)+\notag\\
     &+2\cdot 3+2\cdot 4+...+2\cdot(n-1)+\notag\\
     &+3\cdot 4+3\cdot 5+...+3\cdot(n-1)+\notag\\
     &\dots \notag\\
     &+(n-3)(n-2)+(n-3)(n-1)+\notag\\
     &+(n-2)(n-1)) = \frac{1}{n^4}\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}i\cdot j \\
\text{Which also} \notag\\
a_2 =& \frac{1}{n^4} \left(1\cdot\frac{((n-1)+2)((n-1)-2+1)}{2}+ \right.\notag\\
 &+2\cdot\frac{((n-1)+3)((n-1)-3+1)}{2}+ \notag\\
 &+3\cdot\frac{((n-1)+4)((n-1)-4+1)}{2}+... \notag\\
 &+(n-3)\frac{((n-1)+(n-3+1))((n-1)-(n-3+1)+1)}{2}+\notag\\
 &\left.+(n-2)\frac{((n-1)+(n-2+1))((n-1)-(n-2+1)+1)}{2}\right)\\
=&\frac{1}{n^4}\left(1\frac{(n+1)(n-2)}{2}+2\frac{(n+2)(n-3)}{2}+3\frac{(n+3)(n-4)}{2}\right.\notag\\
 &\left. \dots+(n-3)\frac{(2n-3)(2)}{2}+(n-2)\frac{(2n-2)(1)}{2}\right)
\end{align}
$$

Key insight: notice following:

$$\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}i\cdot j = \sum_{i=1}^{n-2}\sum_{j=1}^{i-1}i\cdot j$$

It simply says:

$$1\cdot 2+1\cdot 3+1\cdot 4+2\cdot 3+2\cdot 4+3\cdot 4 = \\=4\cdot(1+2+3)+3\cdot(1+2)+2\cdot(1)$$

From now on I'll denote n choose k as usual:
$${n \choose k} = C_n^k = \frac{n!}{k!(n-k)!}$$

With this notation we have:
$$\begin{align}a_2 &= \frac{1}{n^4}\left((n-1){n-1 \choose 2}+(n-2){n-2 \choose 2}+\dots+2{2 \choose 2}\right)\\
&= \frac{1}{n^4}\sum_{i=2}^{n-1}i{i \choose 2}
\end{align}$$

Notice that in terms of n choose k we multiply numerator by n once more. In other words each of elements looks like:

$$\frac{n\cdot n!}{k!(n-k)!} = n{n \choose k}$$

But if we add n choose k once more we have:

$$\frac{n\cdot n!+n!}{k!(n-k)!} = n{n \choose k}+{n \choose k}$$
$$\frac{(n+1)!}{k!(n-k)!} = n{n \choose k}+{n \choose k}$$

Now left side looks almost like (n+1) choose (k+1), only missing division by (k+1). Thus

$$(k+1){n+1 \choose k+1} = n{n \choose k}+{n \choose k}$$

Rearrange:

$$\begin{align}n{n \choose k} = (k+1){n+1 \choose k+1} - {n \choose k}\end{align}$$

Now, use this formula for $a_2$:

$$\begin{align}a_2 &= \frac{1}{n^4}\sum_{i=2}^{n-1}i{i \choose 2} = \frac{1}{n^4}\sum_{i=2}^{n-1}\left(3{i+1 \choose 3} - {i \choose 2}\right)\end{align}$$

There happens to be nice formula for sum of n chose k for fixed k. Derivation of it is out of scope. But here it is:

$$\begin{align} \sum_{i=k}^n{i \choose k} = {n+1 \choose k+1}\end{align}$$

Apply this formula:

$$\begin{align}a_2 &= \frac{1}{n^4}\sum_{i=2}^{n-1}\left(3{i+1 \choose 3} - {i \choose 2}\right) =\frac{1}{n^4}\left(3{n+1 \choose 4} - {n \choose 3}\right)\end{align}$$

So far we have:

$$\begin{align} a_0 &= 1 \notag\\
 a_1 &= \frac{n-1}{2n} = \frac{1}{n^2}\frac{n(n-1)}{2} \notag\\
 a_2 &= \frac{1}{n^4}\left(3{n+1 \choose 4} - {n \choose 3}\right) \notag
\end{align}$$

From now on, let $b_k = a_k\cdot n^{2k}$ just to get rid of this term in next formulas. Take a look on $a_3$. It looks like:

$$ 5\cdot 4\cdot(3 + 2 + 1) + 5\cdot 3\cdot(2 + 1) + 5\cdot 2\cdot(1) + 4\cdot 3\cdot(2 + 1) + 4\cdot 2 \cdot 1 + 3\cdot 2 \cdot 
 1\\
=5\cdot (4\cdot(3 + 2 + 1) + 3\cdot(2 + 1) + 2\cdot(1)) + 4\cdot (3\cdot(2 + 1) + 2 \cdot (1)) + 3\cdot(2\cdot 1)$$

Notice that 5 multiplied by term $b_2$ of $f_{n-1}$. But we know that it will be:

$$\left.\left(3{n+1 \choose 4} - {n \choose 3}\right)\right|_{n=5}  = 3{6 \choose 4} - {5 \choose 3} = 3\cdot 15 - 10 = 35 $$

So, actual $b_3$ happens to be:
$$\begin{align} b_3 = \sum_{i=3}^{n-1}i\left(3{i+1 \choose 4} - {i \choose 3}\right) \end{align}$$

Here are two sums. For second sum we have the formula already. For first sum we can basically do everything again just using additional variable for multiplicator.

$$\begin{align} m{n \choose k} &= \frac{m (n!)}{k!(n-k)!} = \frac{(m+n+1-n-1)(n!)}{k!(n-k)!} = \notag\\
m{n \choose k} &= (k+1){n+1 \choose k+1} + (m-n-1){n \choose k} \end{align}$$

Feel the power of the formula!

$$\begin{align} b_3 &= \sum_{i=3}^{n-1}i\left(3{i+1 \choose 4} - {i \choose 3}\right) = \notag\\
&= 3\sum_{i=3}^{n-1}\left(5{i+2 \choose 5}+(i-(i+1)-1){i+1 \choose 4}\right) - \notag\\
& - \sum_{i=3}^{n-1}\left(4{i+1 \choose 4} - {i \choose 3}\right) = \notag\\
&= 15\sum_{i=3}^{n-1}{i+2 \choose 5}-6\sum_{i=3}^{n-1}{i+1 \choose 4}-4\sum_{i=3}^{n-1}{i+1 \choose 4}+\sum_{i=3}^{n-1}{i \choose 3} \\
b_3 &= 15{n+2 \choose 6}-10{n+1 \choose 5}+{n \choose 4}\end{align}
$$

Similarly:

$$\begin{align} b_4 &= \sum_{i=4}^{n-1}i\left(15{i+2 \choose 6} - 10{i+1 \choose 5} + {i \choose 4}\right) = \notag\\
&= 15\sum_{i=4}^{n-1}i{i+2 \choose 6}-10\sum_{i=4}^{n-1}i{i+1 \choose 5} + \sum_{i=4}^{n-1}i{i \choose 4}\notag\\
&= 15\sum_{i=4}^{n-1}\left(7{i+3 \choose 7}-3{i+2 \choose 6}\right) - \notag\\
&- 10\sum_{i=4}^{n-1}\left(6{i+2 \choose 6}-2{i+1 \choose 5}\right)+ \notag \\
&+ \sum_{i=4}^{n-1}\left(5{i+1 \choose 5}-{i \choose 4} \right) \notag\\
b_4 &= 105\sum_{i=4}^{n-1}{i+3 \choose 7}-105\sum_{i=4}^{n-1}{i+2 \choose 6}+25\sum_{i=4}^{n-1}{i+1 \choose 5}-\sum_{i=4}^{n-1}{i \choose 4} \\
b_4 &= 105{n+3 \choose 8}-105{n+2 \choose 7}+25{n+1 \choose 6}-{n \choose 5} \\
\end{align}
$$

Next terms easier calculated making table:
$$\begin{align}
105&& 9 && -4 \notag\\
-105&& 8 && -3 \notag\\
25&& 7 && -2 \notag\\
-1&& 6 && -1 \notag\\
\end{align} \\
b_5 = 945{n+4 \choose 10}-1260{n+3 \choose 9}+490{n+2 \choose 8}-56{n+1 \choose 7}+{n \choose 6}
$$

And we are interested in highest term of each $b_k$ which is:
$$1,\;\; 3,\;\; 15,\;\; 105,\;\; 945,\;\;...\\
1,\;\; 1\cdot 3,\;\; 1\cdot 3\cdot 5,\;\; 1\cdot 3\cdot 5\cdot 7,\;\;... = \frac{n!}{2\cdot 4\cdot 6...} = \frac{n!}{2^{x}\cdot 1\cdot 2\cdot 3\cdot 4...}$$

Also we need to take into account denominator comming from factorial. So, if limit exists then answer is:

$$\begin{align}1 + \sum_{k=1}^\infty \left(\frac{(2k-1)!}{2^{k-1}((k-1)!)}\cdot\frac{1}{(2k)!}\right) = 1 + \sum_{k=1}^\infty\frac{1}{2^{k-1}((k-1)!2k)} = \\
 = 1 + \sum_{k=1}^\infty\frac{1}{2^k(k!)}\end{align}$$

Now, recall that

$$\begin{align}\exp(x) = 1 + \sum_{i=1}^\infty\frac{1}{i!}x^i\end{align}$$

This means if you plug in $2^{-1}$ you get the answer (if it exists).

$$\begin{align}
\lim_{n\to\infty}\prod_{k=1}^{n-1}\frac{n^2+k}{n^2} = \exp\left(\frac{1}{2}\right) = 1.648721\dots
\end{align}$$

Mon, 31 Aug 2020 19:49 GMT