---
title: "Induction: sum of k·k! = (n+1)!−1"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:induction-factorial-sum"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/induction-factorial-sum
site: BCT Engineering
---

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

Theory of Computation · Chapter 1: Introduction

- Asked in: 2072 Chaitra; 2073 Shrawan (asked 2 times)
- Video: [Mathematical Induction Proof for the Sum of Squares](https://www.youtube.com/watch?v=JiBd5yyYfUE) — The Math Sorcerer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/induction-factorial-sum
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

Use mathematical induction to prove that 1·1! + 2·2! + 3·3! + ... + n·n! = (n+1)! − 1 for n ≥ 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.

## Answer

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:

```text
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.

```text
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. ∎

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In proving 1·1! + ... + n·n! = (n+1)! − 1, what does the basis n = 1 check?
   A. LHS = 1 and RHS = 1! − 1 = 0, so they match after adjusting
   B. That the formula holds for every n at once
   C. That (k+1)! − 1 + (k+1)·(k+1)! = (k+2)! − 1
   D. LHS = 1·1! = 1 and RHS = 2! − 1 = 1, so they match
   Answer: D. The basis evaluates both sides at the smallest n and shows they are equal: 1 = 2 − 1. (Key point: Basis step)

2. In the induction step, how is the sum up to (k+1)·(k+1)! rewritten?
   A. Assume the result for k+1 directly and cancel both sides
   B. Replace the first k terms by (k+1)! − 1 and add (k+1)·(k+1)!
   C. Multiply (k+1)! − 1 by (k+1)
   D. Replace the first k terms by (k+2)! − 1 and add (k+1)·(k+1)!
   Answer: B. The hypothesis P(k) gives the sum of the first k terms as (k+1)! − 1; then the new last term is added. (Key point: Use of hypothesis)

3. After substitution we have (k+1)! − 1 + (k+1)(k+1)!. What is the key algebraic step to reach (k+2)! − 1?
   A. Factor (k+1)! to get (k+1)!(1 + k + 1) − 1 = (k+2)(k+1)! − 1
   B. Factor (k+1) to get (k+1)(k! + (k+1)!) − 1
   C. Expand (k+1)! as k! + 1
   D. Subtract 1 from both sides to cancel the −1
   Answer: A. Taking (k+1)! common gives (k+2)·(k+1)! − 1, and (k+2)(k+1)! = (k+2)!. (Key point: Factoring step)

## Related in Theory of Computation

- [Induction: 5^n − 1 divisible by 4](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-five-power) — Theory of Computation, chapter 1, asked 2×
- [Induction: n⁴ − 4n² divisible by 3](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-n4-4n2) — Theory of Computation, chapter 1, asked 2×

## Related in other subjects

- [Induction: sum of geometric progression](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-geometric-series-sum) — Discrete Structure, chapter 1
- [Induction: sum of n(n+1)(n+2)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-product-n-n1-n2) — Discrete Structure, chapter 1
- [Induction: sum of cubes](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-of-cubes) — Discrete Structure, chapter 1, asked 2×
- [Induction: sum of squares](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-of-squares) — Discrete Structure, chapter 1, asked 2×