# How to prove that $1+\frac11(1+\frac12(1+\frac13(…(1+\frac1{n-1}(1+\frac1n))…)))=1+\frac1{1!}+\frac1{2!}+\frac1{3!}+…+\frac1{n!}$?

I'm trying to prove that

$$1+\frac11(1+\frac12(1+\frac13(...(1+\frac1{n-1}(1+\frac1n))...)))=1+\frac1{1!}+\frac1{2!}+\frac1{3!}+...+\frac1{n!}$$

Using induction, suppose that

$$1+\frac11(1+\frac12(1+\frac13(...(1+\frac1{n-2}(1+\frac1{(n-1)}))...)))=1+\frac1{1!}+\frac1{2!}+...+\frac1{(n-1)!}$$

Then

$$1+\frac11(1+\frac12(1+\frac13(...(1+\frac1{n-2}(1+\frac1{n-1}(1+\frac 1n))...)))\\ =1+\frac11(1+\frac12(1+\frac13(...(1+\frac1{n-2}(1+\frac1{n-1}+\frac1{(n-1)n})...)))\\ =(1+\frac1{1!}+\frac1{2!}+...+\frac1{(n-1)!})+\frac1{n!}$$

But I couldn't completely justify the last equality. Could anyone explain this for me, please? Thanks!

Let $f_k(x)=1+\frac{x}{k}$ and show the following more general identity: for $m\geq 0$ and $d\geq 0$: $$f_{m+1}(f_{m+2}(\dots (f_{m+d}(1))\dots))=m!\sum_{k=m}^{m+d}\frac{1}{k!}.$$ We use induction with respect to $d$. It is true for $d=0$ and for $d>0$, \begin{align}f_{m+1}(f_{m+2}(\dots (f_{m+d}(1))\dots)) &=f_{m+1}(f_{(m+1)+1}(\dots (f_{(m+1)+d-1}(1))\dots))\\ &=f_{m+1}\left((m+1)!\sum_{k=m+1}^{m+1+d-1}\frac{1}{k!}\right)\\ &=1+\frac{(m+1)!}{m+1}\sum_{k=m+1}^{m+1+d-1}\frac{1}{k!}\\ &=1+m!\sum_{k=m+1}^{m+d}\frac{1}{k!}=m!\sum_{k=m}^{m+d}\frac{1}{k!}. \end{align}

• Nice approach :). Funnily, although you deal with a more general case, I don't think your answer is harder to parse as the others. – Surb Jun 21 '18 at 12:52

For the last equality, its just simply multiplying

$$1+\frac11(1+\frac12(1+\frac13(1+\frac14(...(1+\frac1{n-2}(1+\frac1{n-1}+\frac1{(n-1)n})...)))))$$ $$=1+\frac11+\frac11\frac12 +\frac11\frac12\frac13+\frac11\frac12\frac13\frac14 + \dots + \frac11 \frac12 \cdots \frac1{n-1}\frac1{n}\\ =1+\frac1{1!}+\frac1{2!}+\frac1{3!}+\frac1{4!}...+\frac1{n!}$$

You can also start calculating the inner bracket first:

\begin{align} &1+\frac11\left(1+\frac12\left(1+\cdots + \frac1{n-2}\left(1+\frac1{n-1}\left(1+\frac1n\right)\cdots\right)\cdots\right)\right) \\&= 1+\frac11\left(1+\frac12\left(1+\cdots + \frac1{n-2}\left(1+\frac{n+1}{n(n-1)}\right)\cdots\right)\right) \\&= 1+\frac11\left(1+\frac12\left(1+\cdots + \frac1{n-3}\left(1+\frac{n(n-1) + n+1}{n(n-1)(n-2)}\right)\cdots\right)\right) \\ &= 1+\frac11\left(1+\frac12\left(1+\cdots + \frac1{n-4}\left(1+\frac{n(n-1)(n-2) +n(n-1) + n+1}{n(n-1)(n-2)(n-3)}\right)\cdots\right)\right) \\ &= \cdots\\ &= \frac{n(n-1)(n-2) \cdots 2 \cdot 1 + n(n-1)(n-2) \cdots 3\cdot2 + \cdots n(n-1)(n-2) + n(n-1) + n+1}{n(n-1)(n-2) \cdots 2 \cdot 1} \\ &= 1 + \frac1{1!} + \frac1{2!} + \cdots + \frac1{(n-3)!} + \frac1{(n-2)!} + \frac1{(n-1)!} + \frac1{n!} \end{align}

The proposition that is adapted for the induction in this case is the following one, which is defined for all natural $n\ge 1$:

$P(n)$:

For all finite sequences $(a_k)_{1\le k\le n}$ of variables we have the equality: $$1+a_1(1+a_2(\dots(1+a_{n-1}(1+a_n))\dots)) = 1+a_1+a_1a_2+\dots+a_1a_2\dots a_n\ .$$

The proposition $P(1)$ is true, it claims for the variable $a_1$ the equality $1+a_1=1+a_1$. We assume $P(n)$ true. To have an easy application of $P(n)$, we make a choice of $(n+1)$ variables of the shape $$(a_k)_{0\le k\le n}\ ,$$ so we start with a new variable rather than ending with a new one. We compute than: \begin{aligned} &1+a_0(\underbrace{1+a_1(1+a_2(\dots(1+a_{n-1}(1+a_n)\dots))}_{\text{Use P(n) for this part}}) \\ &\qquad = 1+a_0(1+a_1+a_1a_2+\dots+a_1a_2\dots a_n) \\ &\qquad = 1+a_0+a_0a_1+a_0a_1a_2+\dots+a_0a_1a_2\dots a_n \ . \end{aligned} We have shown for every $n\ge 1$ the implication $P(n)\Rightarrow P(n+1)$. By induction... $\square$

So the idea was to slightly generalize, then have an easy game in the new setting.