Proving $1\cdot1! + 2\cdot2! + 3\cdot3! + ... + k\cdot k! = (k+1)! - 1$

Question

How could one prove by induction that: $$\forall{n}\in{N}:1(1!)+2(2!)+3(3!)+...+n(n!)=(n+1)!-1$$

My attempt so far:

Base case: Let n = 1, 1(1!) = (2)! - 1 = 1, holds true for LHS = RHS.

Inductive hypothesis: Assume true for n=k, such that:

$$\forall{k}\in{N}:1(1!)+2(2!)+3(3!)+...+k(k!)=(k+1)!-1$$

Inductive step: Let n = k + 1:

$$(k+2)! - 1 = (k+2)(k+1)! - 1 = (k+2)(k+1)(k)! - 1$$

...And now I'm stuck. The fact that the LHS is a summation throws me off, and can't seem to figure out how to continue (or whether I even worked with the "more correct" side of the equation).

Answer 1

You're on the right track but we need to use our assumption. I also prefer starting with the complicated side.

$\Sigma_{i=1}^{k+1} (i*(i!))=(k+1)(k+1)!+\Sigma_{i=1}^{k} (i*(i!))=(k+1)(k+1)!+(k+1)!-1=(k+1+1)(k+1)!-1=(k+2)!-1$

Answer 2

While the OP is requesting a proof by induction, I thought it would be instructive to see another way forward. To that end, we note that

$$kk!=(k+1)!-k! \tag 1$$

whereupon summing both sides of $(1)$ reveals that

$$\begin{align} \sum_{k=1}^{n}kk!&=\sum_{k=1}^{n}\left((k+1)!-k!\right) \tag2 \\\\ &=(n+1)!-1 \end{align}$$

since the sum on the right-hand side of $(2)$ is telescoping. And we are done!