Proving Equalities

Proving equalities with mathematical induction is the most common application. Such problems usually involve summation formulas, product formulas, or recurrence relations.

Proof Strategy

The steps to prove the equality f(n)=g(n)f(n) = g(n):

  1. Base case: verify that f(n0)=g(n0)f(n_0) = g(n_0)
  2. Inductive hypothesis: assume f(k)=g(k)f(k) = g(k)
  3. Inductive step: use the inductive hypothesis to prove f(k+1)=g(k+1)f(k+1) = g(k+1)

Worked Examples

Example 1: Sum of a Geometric Sequence

Proposition: prove that 1+2+22+⋯+2n−1=2n−11 + 2 + 2^2 + \cdots + 2^{n-1} = 2^n - 1

Proof:

Base case: when n=1n = 1, the left side =1= 1 and the right side =21−1=1= 2^1 - 1 = 1, holds.

Inductive hypothesis: assume 1+2+22+⋯+2k−1=2k−11 + 2 + 2^2 + \cdots + 2^{k-1} = 2^k - 1

Inductive step:

1+2+22+⋯+2k−1+2k=(2k−1)+2k(inductive hypothesis)=2⋅2k−1=2k+1−1\begin{aligned} &1 + 2 + 2^2 + \cdots + 2^{k-1} + 2^k \\ &= (2^k - 1) + 2^k \quad \text{(inductive hypothesis)} \\ &= 2 \cdot 2^k - 1 \\ &= 2^{k+1} - 1 \end{aligned}

Conclusion: by mathematical induction, the equality holds.

Example 2: The Sum of Cubes Formula

Proposition: prove that 13+23+33+⋯+n3=[n(n+1)2]21^3 + 2^3 + 3^3 + \cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2

Proof:

Base case: when n=1n = 1, the left side =1= 1 and the right side =[1×22]2=1= \left[\frac{1 \times 2}{2}\right]^2 = 1, holds.

Inductive hypothesis: assume 13+23+⋯+k3=[k(k+1)2]21^3 + 2^3 + \cdots + k^3 = \left[\frac{k(k+1)}{2}\right]^2

Inductive step:

13+23+⋯+k3+(k+1)3=[k(k+1)2]2+(k+1)3=k2(k+1)24+(k+1)3=k2(k+1)2+4(k+1)34=(k+1)2[k2+4(k+1)]4=(k+1)2(k2+4k+4)4=(k+1)2(k+2)24=[(k+1)(k+2)2]2\begin{aligned} &1^3 + 2^3 + \cdots + k^3 + (k+1)^3 \\ &= \left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3 \\ &= \frac{k^2(k+1)^2}{4} + (k+1)^3 \\ &= \frac{k^2(k+1)^2 + 4(k+1)^3}{4} \\ &= \frac{(k+1)^2[k^2 + 4(k+1)]}{4} \\ &= \frac{(k+1)^2(k^2 + 4k + 4)}{4} \\ &= \frac{(k+1)^2(k+2)^2}{4} \\ &= \left[\frac{(k+1)(k+2)}{2}\right]^2 \end{aligned}

Conclusion: by mathematical induction, the equality holds.

Example 3: A Recurrence Sequence

Proposition: the sequence {an}\{a_n\} satisfies a1=1a_1 = 1 and an+1=2an+1a_{n+1} = 2a_n + 1. Prove that an=2n−1a_n = 2^n - 1.

Proof:

Base case: when n=1n = 1, a1=1=21−1a_1 = 1 = 2^1 - 1, holds.

Inductive hypothesis: assume ak=2k−1a_k = 2^k - 1

Inductive step:

ak+1=2ak+1=2(2k−1)+1(inductive hypothesis)=2k+1−2+1=2k+1−1\begin{aligned} a_{k+1} &= 2a_k + 1 \\ &= 2(2^k - 1) + 1 \quad \text{(inductive hypothesis)} \\ &= 2^{k+1} - 2 + 1 \\ &= 2^{k+1} - 1 \end{aligned}

Conclusion: by mathematical induction, an=2n−1a_n = 2^n - 1 for all n≥1n \geq 1.

Practice Problems

Exercise 1

Prove: 1×2+2×3+3×4+⋯+n(n+1)=n(n+1)(n+2)31 \times 2 + 2 \times 3 + 3 \times 4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}

mathematical inductionequality proof

Approach: Use mathematical induction: verify the equality for n=1n = 1, then carry the induction hypothesis over to the n+1n + 1 case.

Steps:

Base case: when n=1n = 1, the left side =1×2=2= 1 \times 2 = 2 and the right side =1×2×33=2= \frac{1 \times 2 \times 3}{3} = 2, holds.

Inductive hypothesis: assume the equality holds for n=kn = k.

Inductive step:

1×2+⋯+k(k+1)+(k+1)(k+2)=k(k+1)(k+2)3+(k+1)(k+2)=k(k+1)(k+2)+3(k+1)(k+2)3=(k+1)(k+2)(k+3)3\begin{aligned} &1 \times 2 + \cdots + k(k+1) + (k+1)(k+2) \\ &= \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) \\ &= \frac{k(k+1)(k+2) + 3(k+1)(k+2)}{3} \\ &= \frac{(k+1)(k+2)(k+3)}{3} \end{aligned}

Conclusion: by mathematical induction, the equality holds.

Answer: By mathematical induction, the equality holds.

Exercise 2

Prove: 11×2+12×3+⋯+1n(n+1)=nn+1\frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}

mathematical inductionequality proof

Approach: Use mathematical induction: verify the equality for n=1n = 1, then carry the induction hypothesis over to the n+1n + 1 case.

Steps:

Base case: when n=1n = 1, the left side =12= \frac{1}{2} and the right side =12= \frac{1}{2}, holds.

Inductive hypothesis: assume the equality holds for n=kn = k.

Inductive step:

11×2+⋯+1k(k+1)+1(k+1)(k+2)=kk+1+1(k+1)(k+2)=k(k+2)+1(k+1)(k+2)=k2+2k+1(k+1)(k+2)=(k+1)2(k+1)(k+2)=k+1k+2\begin{aligned} &\frac{1}{1 \times 2} + \cdots + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} \\ &= \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} \\ &= \frac{k(k+2) + 1}{(k+1)(k+2)} \\ &= \frac{k^2 + 2k + 1}{(k+1)(k+2)} \\ &= \frac{(k+1)^2}{(k+1)(k+2)} \\ &= \frac{k+1}{k+2} \end{aligned}

Conclusion: by mathematical induction, the equality holds.

Answer: By mathematical induction, the equality holds.

Exercise 3

The sequence {an}\{a_n\} satisfies a1=2a_1 = 2 and an+1=3an−2a_{n+1} = 3a_n - 2. Prove that an=2na_n = 2^n.

mathematical inductionequality proof

Approach: First derive the general term of the sequence from the recurrence, then use mathematical induction to check that this general term satisfies both the recurrence and the initial condition.

Steps:

Base case: when n=1n = 1, a1=2=21a_1 = 2 = 2^1, holds.

Inductive hypothesis: assume ak=2ka_k = 2^k

Inductive step:

ak+1=3ak−2=3⋅2k−2=3⋅2k−21=2(3⋅2k−1−1)\begin{aligned} a_{k+1} &= 3a_k - 2 \\ &= 3 \cdot 2^k - 2 \\ &= 3 \cdot 2^k - 2^1 \\ &= 2(3 \cdot 2^{k-1} - 1) \end{aligned}

This method is not quite right. Let us verify: a2=3×2−2=4=22a_2 = 3 \times 2 - 2 = 4 = 2^2 ✓

Re-prove:

ak+1=3ak−2=3⋅2k−2\begin{aligned} a_{k+1} &= 3a_k - 2 \\ &= 3 \cdot 2^k - 2 \end{aligned}

We need to show that this equals 2k+12^{k+1}. But 3⋅2k−2≠2k+13 \cdot 2^k - 2 \neq 2^{k+1}.

Let me verify: a3=3×4−2=10≠8a_3 = 3 \times 4 - 2 = 10 \neq 8

So an=2na_n = 2^n does not hold. The correct general term should be an=2n+2n−1=3⋅2n−1a_n = 2^n + 2^{n-1} = 3 \cdot 2^{n-1}…

Actually, let me recalculate: a1=2,a2=4,a3=10a_1 = 2, a_2 = 4, a_3 = 10…

By working out the recurrence, one can discover that an=2⋅3n−1a_n = 2 \cdot 3^{n-1}.

Answer: The claim to be proved, an=2na_n = 2^n, does not hold: a2=3×2−2=4=22a_2 = 3 \times 2 - 2 = 4 = 2^2 happens to match, but a3=3×4−2=10≠23=8a_3 = 3 \times 4 - 2 = 10 \neq 2^3 = 8. The fixed-point method gives the correct general term an=3n−1+1a_n = 3^{n-1} + 1 (check: a1=2a_1 = 2, and 3(3n−1+1)−2=3n+13(3^{n-1} + 1) - 2 = 3^n + 1).


Summary

Symbols Used in This Article

Symbol notation
SymbolTypePronunciation/ExplanationMeaning in This Article
f(n),g(n)f(n), g(n)Mathematical symbolf/g of nThe expressions on the two sides of the equality
n,kn, kMathematical symboln, kNatural numbers
ana_nMathematical symbola-sub-nThe nnth term of a sequence
{an}\{a_n\}Mathematical symbolset of a-sub-nA sequence
⋯\cdotsMathematical symboland so onEllipsis
n(n+1)2\frac{n(n+1)}{2}Mathematical symboln(n+1) over 2The sum of the first nn natural numbers
∑\sumMathematical symbolsumThe summation symbol

Found an issue with this content?

Tell us what could be improved.