Lesson 3: Proving sum formulas by induction

Prove ∑j=02n+12j=22n+2−1\sum_{j=0}^{2n+1} 2^j = 2^{2n+2} - 1

SkillsProving sum formulas by inductionSigma notation

Worked example

  • Complex unfamiliar
  • Technology free

The syllabus writes ∑j=02n+12j=20+21+22+⋯+22n+1\sum_{j=0}^{2n+1} 2^j = 2^0 + 2^1 + 2^2 + \cdots + 2^{2n+1}. Prove by mathematical induction that

∑j=02n+12j=22n+2−1\sum_{j=0}^{2n+1} 2^j = 2^{2n+2} - 1

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

1 of 5 steps
  1. Step 1: Initial statement

    Let P(n)P(n) be the statement ∑j=02n+12j=22n+2−1\sum_{j=0}^{2n+1} 2^j = 2^{2n+2} - 1, n∈Z+n \in \mathbb{Z}^+. When n=1n = 1 the upper limit is 33: LHS =20+21+22+23=15= 2^0 + 2^1 + 2^2 + 2^3 = 15 and RHS =24−1=15= 2^4 - 1 = 15. So P(1)P(1) is true.

Try a similar one

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

Method

  1. Work out how the limits change from n=kn = k to n=k+1n = k + 1.

  2. Split off every new term, not just one.

  3. Use the assumption on the rest, then simplify to the target.

Watch out for

  • Adding only one new term, 22k+22^{2k+2} or 22k+32^{2k+3}.

  • Writing 22k+2+22k+2=24k+42^{2k+2} + 2^{2k+2} = 2^{4k+4}. Adding two equal powers doubles them: 22k+32^{2k+3}.

Save your progress with a free account