# Induction Proof using factorials

Recall that for $n \in N$, $n! = 1 \cdot 2 \cdots n$.

Prove the following for each $n \in N$:

$$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$$

I understand how to do the proof, but in the inductive step I am facing some difficulty proving the left-hand side is equivalent to the right-hand side.To be direct I am facing some difficulty with the algebra required to make LHS = RHS.

Here is what I have done so far:

1) Base Case

$n = 1$

LHS:

$1/2$

and RHS is $1/2$ $\checkmark$

2) Inductive Step

For $k \geq 1$, Assume $n = k$

$$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{k}{(k+1)!} = 1 - \frac{1}{(k+1)!}$$

$$n = k + 1$$

$$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!} + \frac{k+1}{(k+2)!} = 1 - \frac{1}{(n+1)!}$$

$$\implies 1-\frac{1}{(k+1)!} + \frac{k+1}{(k+2)!} = 1 - \frac{1}{(k+2)!}$$

Here is where i do not know how to make the LHS = RHS.

• You can ignore the 1, since it's the same on both sides. Next you need to take the LHS and add them up! Hint: multiply top and bottom of each to make the denominator of both $(k+2)!$ – Dr Xorile Jul 21 '15 at 2:45
• Can you please show me I have tried that before but don't seem to get a valid solution. – Arjun Dhiman Jul 21 '15 at 2:46
• $1/(k+1)! = (k+2)/(k+2)!$ – Dr Xorile Jul 21 '15 at 2:47
• You were supposed to add (k+1)/(k+2)! And simplify but you just added on the LHS and not RHS – DOCTOR NGILAZI BANDA JOSHUA Jul 21 '15 at 2:48
• can you fix the proof? @DOCTORNGILAZIBANDAJOSHUA – Arjun Dhiman Jul 21 '15 at 2:48

## 3 Answers

$$1-\frac{1}{(k+1)!}+\frac{k+1}{(k+2)!}$$ Note that to simplify this we need a common denominator. Let it be $(k+2)!$. Recall that $(k+1)! = (k+1)(k)(k-1)(k-2) \cdots$ So to get a $(k+2)!$ in the denominator of the fraction we must multiply the numerator and denominator by $k+2$ and get: \begin{align*} 1-\frac{k+2}{(k+2)!} + \frac{k+1}{(k+2)!} &=1-(\frac{k+2}{(k+2)!} - \frac{k+1}{(k+2)!}) \\ &=1-(\frac{k+2-k-1}{(k+2)!}) \\ &= 1-\frac{1}{(k+2)!} \\ \end{align*}

• Yeah, that makes sense. – Arjun Dhiman Jul 21 '15 at 3:09

HINT: we have to show that $$\frac{(k+1)}{(k+2)!}-\frac{1}{(k+1)!}=-\frac{1}{(k+2)!}$$ this is true since $$\frac{(k+1)}{(k+1)!(k+2)}-\frac{1}{(k+1)!}=\frac{1}{(k+1)!}\left(\frac{k+1}{k+2}-1\right)=\frac{1}{(k+1)!}\left(\frac{k+1-k-2}{k+2)}\right)=-\frac{1}{(k+1)!(k+2)}=-\frac{1}{(k+2)!}$$

• What happened to the 1? – Arjun Dhiman Jul 21 '15 at 3:07
• the $1$ was subtracted on both sides of the equation, is this a problem? – Dr. Sonnhard Graubner Jul 21 '15 at 3:10
• @Zero it just got subtracted from both sides of the equation. – Nikhil Jul 21 '15 at 3:10
• Yes, I understand this now. Thank You. – Arjun Dhiman Jul 21 '15 at 3:15
• don't forget the "downvoting" – Dr. Sonnhard Graubner Jul 21 '15 at 3:19

For $n=1,2,3$ we have: \begin{eqnarray} \frac{1}{2!}&=&\frac12=1-\frac12=1-\frac{1}{2!}\\ \frac{1}{2!}+\frac{2}{3!}&=&1-\frac{1}{2!}+\frac13=1-\frac16=1-\frac{1}{3!}\\ \frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}&=&1-\frac16+\frac{1}{8}=1-\frac{1}{24}=1-\frac{1}{4!}. \end{eqnarray} If we assume that up to $n=3$, we have $$\sum_{k=1}^n\frac{k}{(k+1)!}=1-\frac{1}{(n+1)!}.$$ Then \begin{eqnarray} \sum_{k=1}^{n+1}\frac{k}{(k+1)!}&=&\sum_{k=1}^n\frac{k}{(k+1)!}+\frac{n+1}{(n+2)!}=1-\frac{1}{(n+1)!}+\frac{n+1}{(n+2)!}\\ &=&1-\frac{n+2-(n+1)}{(n+2)!}=1-\frac{1}{(n+2)!}. \end{eqnarray}