Skip to main content

Induction: sum of k·k! = (n+1)!−1

Short answer

Base case n=1: 1·1! = 1 = 2! – 1. Assuming sum up to k equals (k+1)! – 1, adding (k+1)·(k+1)! yields (k+1)! – 1 + (k+1)·(k+1)! = (k+1)!(k+2) – 1 = (k+2)! – 1.

Use mathematical induction to prove that 1·1! + 2·2! + 3·3! + ... + n·n! = (n+1)! − 1 for n ≥ 1.

We prove P(n): 1·1! + 2·2! + ... + n·n! = (n+1)! − 1 by induction on n ≥ 1.

Basis (n = 1)

LHS = 1·1! = 1. RHS = (1+1)! − 1 = 2 − 1 = 1. So P(1) is true.

Induction hypothesis

Assume P(k) is true for some k ≥ 1:

1·1! + 2·2! + ... + k·k! = (k+1)! − 1

Induction step

We must show P(k+1): the sum up to (k+1)·(k+1)! equals (k+2)! − 1.

LHS = [1·1! + ... + k·k!] + (k+1)·(k+1)!
    = (k+1)! − 1 + (k+1)·(k+1)!        (by hypothesis)
    = (k+1)! [1 + (k+1)] − 1
    = (k+1)! (k+2) − 1
    = (k+2)! − 1                        since (k+2)! = (k+2)(k+1)!
    = RHS of P(k+1)

So P(k) implies P(k+1).

Conclusion

By the principle of mathematical induction, P(n) is true for every n ≥ 1. ∎

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 1 questions →