Proof by induction, 1 · 1! + 2 · 2! + ... + n · n! = (n + 1)! − 1

Question

So I'm supposed to prove that $$1 · 1! + 2 · 2! + \dots + n · n! = (n + 1)! − 1$$ using induction. What I've done

Basic Step:

Let $n=1$, $$1\cdot1! = 1\cdot1 = 1 = (n+1)!-1 = 2!-1 = 2-1 = 1$$

Induction Step:

Assume $f(k) = 1\cdot1! + 2\cdot2! + \dots + k\cdot k! = (k+1)!-1$

\begin{align} F(k+1) &= 1\cdot1! + 2\cdot2! + \dots + k\cdot k! + (k+1)\cdot(k+1)!\\ &= (k+1)!\ - 1 + (k+1)\cdot(k+1)!\\ &= (k+1)!\cdot((k+1) - 1) = (k+1)!\cdot(k) \end{align}

I think I'm supposed to make $(k+1)!\cdot k = ((k+1)+1)!+1 = (k+2)!-1$ but I'm not sure how to get there.

Answer 1

You're supposed to prove that $$(k+1)!-1+(k+1)(k+1)!=(k+2)!\,\color{red}{\mathbf -}\,1$$ Simplifying the $- 1$ terms and dividing both sides by $(k+1)!$ yields Simplifying both sides by $(k+1)!$ yields $$1+(k+1)=k+2,$$ which is pretty obvious, isn't it?

Answer 2

Bernard's answer highlights the key algebraic step, but I thought I might mention something that I have found useful when dealing with induction problems: whenever you have an induction problem like this that involves a sum, rewrite the sum using $\Sigma$-notation. It makes everything more concise and easier to manipulate: \begin{align} \sum_{i=1}^{k+1}i\cdot i!&=\sum_{i=1}^k i\cdot i!+(k+1)(k+1)!\tag{by definition}\\[1em] &= [(k+1)!-1]+(k+1)(k+1)!\tag{induction hyp.}\\[1em] &= (k+1)![1+(k+1)]-1\tag{rearrange}\\[1em] &= (k+1)![k+2]-1\tag{simplify}\\[1em] &= (k+2)!-1.\tag{by definition} \end{align}