Induction proves formulas for sums and products. Write P(k+1) as P(k)
Lesson 2 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
prove formulas for sums of squares and cubes by induction;
prove telescoping sums and products of fractions;
guess a formula from small cases and then prove it.
The shape of every sum proof
Let S(n) be the sum of the first n terms of a list, and suppose we want S(n)=F(n) for a formula F. The step always runs the same way.
S(k+1)=S(k)+(term number k+1).
Replace S(k) by F(k). This is where the hypothesis is used.
Show that F(k)+(term k+1)=F(k+1). This is pure algebra.
So the step is a single identity. Factorise early. The common factor is usually (k+1).
The sum of squares
Claim.12+22+⋯+n2=6n(n+1)(2n+1) for every n≥1.
Base case. For n=1: 61×2×3=1=12.
Step. Assume the formula for n=k. Then
12+⋯+k2+(k+1)2=6k(k+1)(2k+1)+(k+1)2.
Take out 6k+1: the bracket left is k(2k+1)+6(k+1)=2k2+7k+6=(k+2)(2k+3).
So the sum is 6(k+1)(k+2)(2k+3). This is the formula with n=k+1, since 2(k+1)+1=2k+3.
By induction the formula holds for every n≥1.
The sum of cubes
The sum of the first n cubes is the square of the sum of the first n numbers:
13+23+⋯+n3=(2n(n+1))2.
In the step, take out 4(k+1)2. What is left is k2+4(k+1)=(k+2)2. Try it yourself in Check yourself.
Telescoping sums
Now take fractions:
1×21+2×31+⋯+n(n+1)1=n+1n.
The step needs k+1k+(k+1)(k+2)1=k+2k+1. Over the common denominator (k+1)(k+2) the top is k(k+2)+1=(k+1)2. Cancel one (k+1), and we are done.
There is also a direct proof: k(k+1)1=k1−k+11, so the terms cancel in pairs. Both proofs are fine. Induction is the safe choice when you cannot see the cancelling.
Products
A product works like a sum, with multiplying in place of adding:
(1+11)(1+21)⋯(1+n1)
=n+1.
The step multiplies k+1 by the next factor 1+k+11=k+1k+2. The result is k+2.
Guess, then prove
Sometimes no formula is given. Then:
work out the first few values;
look for a pattern and write a guess;
prove the guess by induction.
Example. Find 1×1!+2×2!+⋯+n×n!. The values for n=1,2,3,4 are 1, 5, 23, 119. Each is one less than a factorial: 2!−1, 3!−1, 4!−1, 5!−1. So we guess (n+1)!−1. The step adds (k+1)(k+1)! to (k+1)!−1, which gives (k+2)(k+1)!−1=(k+2)!−1.
Practise with new numbers
Try it in Python
The program prints the telescoping sum as exact fractions, so the pattern is easy to see. Then it tests the guess and the sum of squares on many values.
Common mistakes
Adding the wrong term. Term number k+1 of 12+22+… is (k+1)2, not k2+1.
Expanding everything. Large expansions hide the target. Take out the common factor first.
Forgetting the base case of a guess. A guessed formula must pass the base case too.
Stopping at the algebra. The last line must say that the result is P(k+1).
Remember these
12+⋯+n2=6n(n+1)(2n+1) and 13+⋯+n3=(2n(n+1))2.
The step: S(k+1)=S(k)+next term, then use the hypothesis.
Telescoping: k(k+1)1=k1−k+11.
No formula given: compute, guess, prove.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Finish the step for the sum of cubes: show that (2k(k+1))2+(k+1)3=(2(k+1)(k+2))2.
What is term number k+1 of the sum 1×3+2×4+3×5+…?
Guess a formula for 21+41+⋯+2n1 and prove the step.
Let Pn=(1−21)⋯(1−n+11). Prove the step for
Pn=n+11.
A student writes the step of the sum of squares as "S(k+1)=S(k)+k2+1". What is wrong?
References
Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle.
Richard Hammack, Book of Proof, third edition, Chapter 10, Mathematical Induction.
Enroll free in Induction for Sums and Divisibility
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.
plus one more term, use the hypothesis, and make the algebra reach the target. The sums of squares and cubes, telescoping sums of fractions and products that cancel are standard. When no formula is given, work out small cases, guess the pattern and then prove it.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself
This lesson is free to read. Enroll free to keep your place and take the tests.