1.7 - Proof by induction for sums

1.7 - Proof by induction for sums

Checking several values can suggest a sum formula, but it cannot establish an infinite collection of cases. In this part of 1.7, you will turn a successful check into a proof, use the next term to prove power sums, and investigate a factorial sum before proving your conjecture.

The induction principle

Why should 1+3+5+⋯+(2n−1)=n21+3+5+\cdots+(2n-1)=n^2 remain true when nn is far beyond anything you have checked? The first few sums are 1,4,9,161,4,9,16. That pattern suggests squares; a proof must explain why the pattern cannot break at the next integer.

Call the statement for a particular index P(n)P(n). A base case establishes the first statement. The inductive step establishes a conditional claim: if one statement is true, the next is true. Together these reach every integer from the starting point.

Mathematical induction

To prove P(n)P(n) for every integer n≥an\geq a:

  1. Verify P(a)P(a).
  2. Assume P(k)P(k) for an arbitrary integer k≥ak\geq a. This is the induction hypothesis.
  3. Use that hypothesis to establish P(k+1)P(k+1).

Conclude that P(n)P(n) holds for every integer n≥an\geq a, by mathematical induction.

The assumption is temporary. You prove that truth passes from an arbitrary case to its successor; the verified base case then starts the chain. You are not assuming the result for every integer.

Worked example 1: why the odd-number sum continues

Question. Prove by induction that ∑r=1n(2r−1)=n2\displaystyle\sum_{r=1}^{n}(2r-1)=n^2 for every positive integer nn.

Plan. Check the first odd number, then add the next odd number to the sum assumed at kk.

For n=1n=1, both sides equal 11, so the base case is true. Assume that, for some arbitrary positive integer kk,

∑r=1k(2r−1)=k2.\sum_{r=1}^{k}(2r-1)=k^2.

The next term is 2(k+1)−1=2k+12(k+1)-1=2k+1, so

∑r=1k+1(2r−1)=∑r=1k(2r−1)+(2k+1)=k2+2k+1use the hypothesis=(k+1)2.\begin{aligned} \sum_{r=1}^{k+1}(2r-1) &=\sum_{r=1}^{k}(2r-1)+(2k+1) \\ &=k^2+2k+1 &&\text{use the hypothesis}\\ &=(k+1)^2. \end{aligned}

This is precisely the statement with n=k+1n=k+1.

Answer. The result is true at 11, and truth at kk implies truth at k+1k+1. It therefore holds for every positive integer nn, by induction.

Check. At n=5n=5, direct addition gives 1+3+5+7+9=25=521+3+5+7+9=25=5^2. This checks the arithmetic in a new case; the induction argument proves all cases.

Change the summand from the odd numbers to the even numbers. The logical structure stays the same, but the new last term and the target formula must both change.

Worked example 2: an even-number sum

Question. Prove by induction that ∑r=1n2r=n(n+1)\displaystyle\sum_{r=1}^{n}2r=n(n+1) for every positive integer nn.

Plan. Add 2(k+1)2(k+1) to the assumed sum and factor out k+1k+1.

At n=1n=1, the sum is 2=1(2)2=1(2). Assume, for an arbitrary positive integer kk, that

∑r=1k2r=k(k+1).\sum_{r=1}^{k}2r=k(k+1).

Then

∑r=1k+12r=k(k+1)+2(k+1)hypothesis and next term=(k+1)(k+2)factor out k+1.\begin{aligned} \sum_{r=1}^{k+1}2r &=k(k+1)+2(k+1) &&\text{hypothesis and next term}\\ &=(k+1)(k+2) &&\text{factor out }k+1. \end{aligned}

The final expression is n(n+1)n(n+1) at n=k+1n=k+1.

Answer. The base case and the implication from kk to k+1k+1 establish the result for every positive integer nn, by induction.

Check. Pairing the terms for n=6n=6 gives (2+12)+(4+10)+(6+8)=42=6(7)(2+12)+(4+10)+(6+8)=42=6(7), using a different summation method.

A base case without a step reaches only one integer. A step without a base case does not establish any starting statement.

Watch out

“Assume the formula is true for every nn” assumes the conclusion. Instead, assume it for an arbitrary allowed kk, and establish the next case from that assumption.

Check which integers a proposed chain actually reaches.

Adding the next term

For a finite sum, the link from kk to k+1k+1 comes from separating the last term.

If Sn=∑r=1nf(r)S_n=\sum_{r=1}^{n}f(r), then Sk+1=Sk+f(k+1)S_{k+1}=S_k+f(k+1). The hypothesis replaces SkS_k, while the term you add is the original summand evaluated at k+1k+1. It is not the proposed sum formula evaluated there.

You already know

The standard sums of rr, r2r^2 and r3r^3 are supplied in MF19. If a question asks you to prove one by induction, quoting it from the booklet does not supply the requested proof.

Before simplifying, write down what you want to reach. For the square-sum formula, the target at k+1k+1 is (k+1)(k+2)(2k+3)/6(k+1)(k+2)(2k+3)/6.

Worked example 3: proving the square-sum formula

Question. Prove by induction that

∑r=1nr2=n(n+1)(2n+1)6\sum_{r=1}^{n}r^2=\frac{n(n+1)(2n+1)}6

for every positive integer nn.

Plan. Add (k+1)2(k+1)^2 to the assumed expression and retain the common factor k+1k+1.

At n=1n=1, the two sides are 11 and 1(2)(3)/6=11(2)(3)/6=1. Assume that, for an arbitrary positive integer kk,

∑r=1kr2=k(k+1)(2k+1)6.\sum_{r=1}^{k}r^2=\frac{k(k+1)(2k+1)}6.

Then

∑r=1k+1r2=k(k+1)(2k+1)6+(k+1)2=k+16(k(2k+1)+6(k+1))=k+16(2k2+7k+6)=(k+1)(k+2)(2k+3)6.\begin{aligned} \sum_{r=1}^{k+1}r^2 &=\frac{k(k+1)(2k+1)}6+(k+1)^2 \\ &=\frac{k+1}{6}\bigl(k(2k+1)+6(k+1)\bigr)\\ &=\frac{k+1}{6}(2k^2+7k+6)\\ &=\frac{(k+1)(k+2)(2k+3)}6. \end{aligned}

The first equality uses the hypothesis; the final factorisation gives exactly the required next case.

Answer. The identity holds for every positive integer nn, by mathematical induction.

Check. At n=4n=4, the original sum is 1+4+9+16=301+4+9+16=30; the formula gives 4(5)(9)/6=304(5)(9)/6=30.

Change only the power in the summand from 22 to 33. The induction link is unchanged, but the common factor is now (k+1)2(k+1)^2.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account