Solving Induction $\prod\limits_{i=1}^{n-1}\left(1+\frac{1}{i}\right)^{i} = \frac{n^{n}}{n!}$

Question

I try to solve this by induction:

$$ \prod_{i=1}^{n-1}\left(1+\frac{1}{i} \right)^{i} = \frac{n^{n}}{n!} $$

This leads me to: $$ \prod_{i=1}^{n+1-1}\left(1+\frac{1}{i}\right)^{i} = \frac{(n+1)^{n+1}}{(n+1)!} = \frac{(n+1)^{n}(n+1)}{n!(n+1)}\\ \prod_{i=1}^{n+1-1}\left(1+\frac{1}{i}\right)^{i} = \frac{(n+1)^{n+1}}{(n+1)!} $$

I tried to solve this that way: $$ \prod_{i=1}^{n-1}\left(1+\frac{1}{i}\right)^{i}\left(1+\frac{1}{n}\right)^{n} = \frac{(n+1)^{n+1}}{(n+1)!} $$

Which is equivalent to: $$ \frac{n^{n}}{n!}\left(1+\frac{1}{n}\right)^{n} = \frac{(n+1)^{n}(n+1)}{n!(n+1)} $$

I'm not sure if every step is right, but now i can't solve this further. Please help :)

Answer 1

Hint $\ $ The LHS and RHS both satisfy $\rm\:f(n+1)/f(n) = (1+1/n)^n,\,\ f(1) = 1.\:$ But it is trivial to prove by induction the uniqueness of solutions of such first-order difference equations, which yields the sought equality: LHS = RHS. As I often emphasize, uniqueness theorems provide powerful tools for proving equalities.

Note that the solution of such recurrences may be represented by (indefinite) products

$$\rm \left[\begin{eqnarray}\rm f(n\!+\!1) \,&=&\rm\, a_n\: f(n)\\ \rm f(1) \,&=&\,1 \end{eqnarray} \right]\,\iff\, f(n)\, =\, \prod_{k=1}^{n-1}\:\! a_k$$

Thus the uniqueness theorem yields that such products are well-defined. It is a gap in most courses that this fact is not proved (making many such inductive proofs circular). For more on "definitions by induction" see the award-winning Monthly exposition of Leon Henkin referenced here and here.

This is a special case of telescopy. For as below we can write the RHS as a product of its term ratios

$$\rm\ g(n)\ =\ \frac{g(n)}{\color{#c00}{g(n-1)}}\ \frac{\color{#c00}{g(n-1)}}{\color{#0a0}{g(n-2)}}\ \frac{\color{#0a0}{g(n-2)}}{\cdots }\ \cdots\ \frac{\cdots}{\color{brown}{g(3)}}\ \frac{\color{brown}{g(3)}}{\color{blue}{g(2)}}\ \frac{\color{blue}{g(2)}}{1}$$

Then the proof amounts to saying that both expressions are equal because they are both products of the same expression (here $\rm\:(1+1/i)^i\:).\:$ The usual ad-hoc induction proof of your problem amounts to essentially proving this uniqueness theorem in this specific case. But here, in fact, proving the general case is simpler than proving the special case, because it is much easier to see the telescopic cancellation without the obfuscating details of the special case. Further, one obtains a general proof that can be reused for all problems of this type. Who could ask for more?

Answer 2

You are almost finished. Note that since $1+\frac{1}{n}=\frac{n+1}{n}$, we have $$\left(1+\frac{1}{n}\right)^n=\frac{(n+1)^n}{n^n}=\frac{(n+1)^{n+1}}{(n+1)n^n}.$$

Remark: The induction argument should be written up in a more formal style. Deal with the base case explicitly. Then do the induction step, showing that if the assertion holds for $n=k$, then it holds for $n=k+1$. Even though it is quite all right to do your "scratch" computations backwards, the writeup should be more direct.

So for the induction step, we assume that for a given $k$, we have $$ \prod_{i=1}^{k-1}\left(1+\frac{1}{i} \right)^{i} = \frac{k^{k}}{k!}\tag{$\ast$}. $$ We want to show that $$ \prod_{i=1}^{k}\left(1+\frac{1}{i} \right)^{i} = \frac{(k+1)^{k+1}}{(k+1)!}. $$

Note that $$ \prod_{i=1}^{k}\left(1+\frac{1}{i} \right)^{i} =\left( \prod_{i=1}^{k-1}\left(1+\frac{1}{i} \right)^{i} \right) \left(1+\frac{1}{k}\right)^k . $$ By the induction assumption $(\ast)$, the right-hand side is equal to $$\frac{k^{k}}{k!}\left(1+\frac{1}{k}\right)^k.$$ Continue.