1

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

Thomas Andrews
  • 177,126
Xian
  • 89
  • 1
    Thanks, that helped me! Didn't find that link while searching earlier. Question solved. I should of worked with the LHS then swapped using the IH. – Xian Oct 11 '15 at 18:51

2 Answers2

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!

Mark Viola
  • 179,405
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$

Konrad Wrobel
  • 459
  • 2
  • 12
  • I understand now, it's actually very simple from the LHS! I should of remembered to swap for the IH assumption. – Xian Oct 11 '15 at 18:59