A brief note on Induction for Sums and Divisibility . Read it before a test. Try each question at the end before you open its answer.
The principle Base case: show P ( n 0 ) P(n_0) P ( n 0 ) , usually P ( 1 ) P(1) P ( 1 ) . Step: assume P ( k ) P(k) P ( k ) for some k ≥ n 0 k \ge n_0 k ≥ n 0 (the inductive hypothesis) and prove P ( k + 1 ) P(k + 1) P ( k + 1 ) . Conclusion: by induction, P ( n ) P(n) P ( n ) holds for every n ≥ n 0 n \ge n_0 n ≥ n 0 . Checking cases is not a proof: n 2 − n + 41 n^2 - n + 41 n 2 − n + 41 is prime for n = 1 n = 1 n = 1 to 40 40 40 and not for n = 41 n = 41 n = 41 . Sums and products Shape of the step: S ( k + 1 ) = S ( k ) + term k + 1 S(k + 1) = S(k) + \text{term}_{k + 1} S ( k + 1 ) = S ( k ) + term k + 1 , then use the hypothesis. Squares: 1 2 + ⋯ + n 2 = n ( n + 1 ) ( 2 n + 1 ) 6 1^2 + \dots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6} 1 2 + ⋯ + n 2 = 6 n ( n + 1 ) ( 2 n + 1 ) . Cubes: 1 3 + ⋯ + n 3 = ( n ( n + 1 ) 2 ) 2 1^3 + \dots + n^3 = \left(\dfrac{n(n + 1)}{2}\right)^2 1 3 + ⋯ + n 3 = ( 2 n ( n + 1 ) ) 2 . Telescoping: 1 k ( k + 1 ) = 1 k − 1 k + 1 \dfrac{1}{k(k + 1)} = \dfrac{1}{k} - \dfrac{1}{k + 1} k ( k + 1 ) 1 = k 1 − k + 1 1 . No formula given: work out small cases, guess, then prove. Divisibility Plan: f ( k + 1 ) = c f ( k ) + ( a clear multiple of d ) f(k + 1) = c\,f(k) + (\text{a clear multiple of } d) f ( k + 1 ) = c f ( k ) + ( a clear multiple of d ) . Trick: multiply f ( k ) f(k) f ( k ) by the base of the power and subtract. Largest divisor: the highest common factor of the first values, then a proof. A worked example Prove that 3 ∣ 4 n − 1 3 \mid 4^n - 1 3 ∣ 4 n − 1 for every n ≥ 1 n \ge 1 n ≥ 1 .
Base. 4 − 1 = 3 4 - 1 = 3 4 − 1 = 3 . Step. 4 k + 1 − 1 = 4 ( 4 k − 1 ) + 3 4^{k + 1} - 1 = 4(4^k - 1) + 3 4 k + 1 − 1 = 4 ( 4 k − 1 ) + 3 . Conclusion. Both parts are multiples of 3 3 3 , so by induction 3 ∣ 4 n − 1 3 \mid 4^n - 1 3 ∣ 4 n − 1 for every n ≥ 1 n \ge 1 n ≥ 1 . Practice with new numbers
A program to try The program tests three results of this note for n = 1 n = 1 n = 1 to 50 50 50 .
Read it first. Then run it. Do all three lines say True?
1. Add a line that tests whether 5 5 5 divides n 5 − n n^5 - n n 5 − n for n = 1 n = 1 n = 1 to 50 50 50 .
Mistakes to avoid No base case. A step alone proves nothing. Assuming P ( k + 1 ) P(k + 1) P ( k + 1 ) . Assume P ( k ) P(k) P ( k ) only. Wrong next term. Term k + 1 k + 1 k + 1 of 1 2 + 2 2 + … 1^2 + 2^2 + \dots 1 2 + 2 2 + … is ( k + 1 ) 2 (k + 1)^2 ( k + 1 ) 2 . Dropping a term when you multiply f ( k ) f(k) f ( k ) by a number. Check yourself What is the base case of 1 + 4 + 7 + ⋯ + ( 3 n − 2 ) = n ( 3 n − 1 ) 2 1 + 4 + 7 + \dots + (3n - 2) = \dfrac{n(3n - 1)}{2} 1 + 4 + 7 + ⋯ + ( 3 n − 2 ) = 2 n ( 3 n − 1 ) ? Stuck? Show a hint Show the answerProve the step for the same formula. Stuck? Show a hint Show the answerWrite 7 k + 1 − 1 7^{k + 1} - 1 7 k + 1 − 1 as 7 ( 7 k − 1 ) 7(7^k - 1) 7 ( 7 k − 1 ) plus a number. Stuck? Show a hint Show the answerFind the largest number that divides 2 2 n − 1 2^{2n} - 1 2 2 n − 1 for every n ≥ 1 n \ge 1 n ≥ 1 . Stuck? Show a hint Show the answerSources Arthur Engel, Problem-Solving Strategies , Chapter 8. Richard Hammack, Book of Proof , Chapter 10.