Tips for Solving Induction Proofs
1. Find a recurrence relation for each of the following expressions.
That is, find an expression for an in terms of an-1
. Then write a recursive procedure in pseudocode for each:
a. G(n) = 5n + 4, n > 0
b. S(n) = n2 - 1, n > 0
c. M(n) = (n + 1)2 , n > 0
Problems 2 and 7 involve the same "trick" in working the inductive step. Otherwise, each of these has been chosen to illustrate a different algebraic technique in working the solution.
2. Prove by induction: 5n - 1 is divisible by 4 for all n ³ 1.
3. Prove by induction: n! > 2n for all n > 3.
4. Prove by induction: The sum of the squares of the positive integers (12 + 22 + 32 +...+n2) = n(n+1)(2n+1)/6.
5. Prove by induction: If a is a constant and r is a real number ¹
1, then
a + ar + ar2 + ar3 + ... +
arn = a( rn+1 - 1) / (r - 1)
for all non-negative n.
6. (Johnsonbaugh) Prove that any amount of postage of 24 cents or more may be obtained using only 5-cent and 7-cent stamps.
7. Prove by induction: 7n - 1 is divisible by 6 for all non-negative
n.
This page copyleft 1999 Brian K. Hare