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

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 :)

-

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.

-
Thank you very much, nice trick ;) You helped a beginner very much :) – blang May 10 '12 at 15:41
Thank you for the structure tip too. Of course i use the induction step and wrote it down better than i did it here :) The main problem is i don't know the english words for induction beginning, step and presumption – blang May 10 '12 at 15:49

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?

-
Sounds good :) Im a total beginner, i have no idea what you mean ;) But thank you – blang May 10 '12 at 15:42
Wow, nice :) Sry i accepted the answer above because it was the direct answer of my question, but this is amazing. I think i will use this stack more often – blang May 10 '12 at 16:00
@blang After you do a few more of these you might find it helpful to revisit this answer. It yields an algorithm for handling problems of this type - removing the need for any guesswork or intuitive leaps. It can be understood at high-school level if explained appropriately. You can find many more examples in my linked posts, both multiplicative and additive. – Bill Dubuque May 10 '12 at 16:02