A brief note on Induction in Algebra, Calculus and Olympiad Problems . Read it before a test. Try each question at the end before you open its answer.
Algebra and calculus Binomial theorem: the step uses Pascal's rule ( k r − 1 ) + ( k r ) = ( k + 1 r ) \binom{k}{r - 1} + \binom{k}{r} = \binom{k + 1}{r} ( r − 1 k ) + ( r k ) = ( r k + 1 ) . Matrix powers: guess from A 2 A^2 A 2 and A 3 A^3 A 3 , prove with A k + 1 = A k A A^{k + 1} = A^kA A k + 1 = A k A . nth derivatives: differentiate the formula for k k k once more. Example: d n d x n ( x e x ) = ( x + n ) e x \dfrac{d^n}{dx^n}(xe^x) = (x + n)e^x d x n d n ( x e x ) = ( x + n ) e x . De Moivre: ( cos θ + i sin θ ) n = cos n θ + i sin n θ (\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta ( cos θ + i sin θ ) n = cos n θ + i sin n θ . Flawed proofs: the checklist A true base case? A working step alone proves nothing. Does the step work for the smallest k k k ? The horses fail from 1 1 1 to 2 2 2 . Enough base cases for a step that looks back further? Does the step end at P ( k + 1 ) P(k + 1) P ( k + 1 ) rather than start from it? A pattern is not a proof: points on a circle give 1 , 2 , 4 , 8 , 16 , 31 1, 2, 4, 8, 16, 31 1 , 2 , 4 , 8 , 16 , 31 . L-shaped tiling: four quarters and one piece in the middle; 4 n − 1 3 \dfrac{4^n - 1}{3} 3 4 n − 1 pieces. Lines: line k k k adds k k k regions, so n 2 + n + 2 2 \dfrac{n^2 + n + 2}{2} 2 n 2 + n + 2 in all. Tower of Hanoi: H ( n ) = 2 H ( n − 1 ) + 1 = 2 n − 1 H(n) = 2H(n - 1) + 1 = 2^n - 1 H ( n ) = 2 H ( n − 1 ) + 1 = 2 n − 1 . Stuck step: strengthen the claim, or induct on another quantity. Practice with new numbers
A program to try The program tests a matrix power formula and prints two region counts.
Read it first. Then run it. Where does the circle count stop doubling?
1. Change A to [[1, 2], [0, 1]] and the formula to [[1, 2 * n], [0, 1]]. Does it still say True?
Mistakes to avoid Raising each entry of a matrix to the power n n n . Dropping a term of the product rule. Trusting a step without testing it at the smallest k k k . Believing a pattern from five cases. Check yourself What is the top-right entry of $ ( 1 2 0 1 ) \displaystyle \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} ( 1 0 2 1 ) ^{7}$?
Stuck? Show a hint Show the answerWhat is the third derivative of x e x xe^x x e x ? Stuck? Show a hint Show the answerHow many L-shaped pieces cover an 8 × 8 8 \times 8 8 × 8 board with one square removed? Stuck? Show a hint Show the answerHow many moves does the Tower of Hanoi need for 3 3 3 discs? Stuck? Show a hint Show the answerSources Arthur Engel, Problem-Solving Strategies , Chapter 8. Richard Hammack, Book of Proof , Chapter 10.