Lesson 1: The idea of proof by induction

Prove 1+2+4+⋯+2n−1=2n−11 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1

SkillsStructure of an induction proofProving sum formulas by induction

Worked example

  • Simple familiar
  • Technology free

Prove by mathematical induction that

1+2+4+⋯+2n−1=2n−11 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1

for all n∈Z+n \in \mathbb{Z}^+.

1 of 6 steps
  1. Step 1: Define P(n)P(n)

    Let P(n)P(n) be the statement 1+2+4+⋯+2n−1=2n−11 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1, for n∈Z+n \in \mathbb{Z}^+.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Define P(n)P(n) and check P(1)P(1) by evaluating both sides.

  2. Assume P(k)P(k) for some k∈Z+k \in \mathbb{Z}^+.

  3. Write the target P(k+1)P(k+1), including the new last term.

  4. Replace the first kk terms using the assumption, then simplify to the target.

  5. Write the conclusion.

Watch out for

  • Writing the new term as 2k+12^{k+1}. The last term of the sum to k+1k + 1 terms is 2(k+1)−1=2k2^{(k+1) - 1} = 2^k.

  • Writing 2k+2k=4k2^k + 2^k = 4^k or 22k2^{2k}. In fact 2k+2k=2×2k=2k+12^k + 2^k = 2 \times 2^k = 2^{k+1}.

Save your progress with a free account