A brief note on Recurrences and Counting by Recursion . Read it before a test. Try each question at the end before you open its answer.
Setting up Name the count a n a_n a n for size n n n . Split on the first or the last step. Each case must be a smaller copy, with no overlaps. Starting values: count the smallest cases by hand. Tower of Hanoi: h n = 2 h n − 1 + 1 h_n = 2h_{n-1} + 1 h n = 2 h n − 1 + 1 , so h n = 2 n − 1 h_n = 2^n - 1 h n = 2 n − 1 . Lines in a plane: r n = r n − 1 + n r_n = r_{n-1} + n r n = r n − 1 + n , so r n = 1 + n ( n + 1 ) 2 r_n = 1 + \dfrac{n(n + 1)}{2} r n = 1 + 2 n ( n + 1 ) . Steps of 1 or 2, domino tilings, strings with no 11: the Fibonacci recurrence. Solving Characteristic equation of a n = p a n − 1 + q a n − 2 a_n = pa_{n-1} + qa_{n-2} a n = p a n − 1 + q a n − 2 : x 2 = p x + q x^2 = px + q x 2 = p x + q . Different roots r , s r, s r , s : a n = A r n + B s n a_n = Ar^n + Bs^n a n = A r n + B s n . Double root r r r : a n = ( A + B n ) r n a_n = (A + Bn)r^n a n = ( A + B n ) r n . Constant term in a n = c a n − 1 + d a_n = ca_{n-1} + d a n = c a n − 1 + d : fixed point L = c L + d L = cL + d L = c L + d , then a n − L = c n ( a 0 − L ) a_n - L = c^n(a_0 - L) a n − L = c n ( a 0 − L ) . Binet: F n = φ n − ψ n 5 F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}} F n = 5 φ n − ψ n , with φ ≈ 1.618 \varphi \approx 1.618 φ ≈ 1.618 . Special numbers Derangements: D n = ( n − 1 ) ( D n − 1 + D n − 2 ) D_n = (n - 1)(D_{n-1} + D_{n-2}) D n = ( n − 1 ) ( D n − 1 + D n − 2 ) , D 1 = 0 D_1 = 0 D 1 = 0 , D 2 = 1 D_2 = 1 D 2 = 1 ; nearest whole number to n ! e \dfrac{n!}{e} e n ! . Exactly k k k fixed: ( n k ) D n − k \dbinom{n}{k}D_{n-k} ( k n ) D n − k . Catalan: C n = 1 n + 1 ( 2 n n ) C_n = \dfrac{1}{n + 1}\dbinom{2n}{n} C n = n + 1 1 ( n 2 n ) : brackets, diagonal paths, triangulations of an ( n + 2 ) (n + 2) ( n + 2 ) -gon. A worked example Solve a n = a n − 1 + 12 a n − 2 a_n = a_{n-1} + 12a_{n-2} a n = a n − 1 + 12 a n − 2 with a 0 = 2 a_0 = 2 a 0 = 2 and a 1 = 1 a_1 = 1 a 1 = 1 .
Equation. x 2 = x + 12 x^2 = x + 12 x 2 = x + 12 , roots 4 4 4 and − 3 -3 − 3 . Fit. A + B = 2 A + B = 2 A + B = 2 and 4 A − 3 B = 1 4A - 3B = 1 4 A − 3 B = 1 , so A = 1 A = 1 A = 1 and B = 1 B = 1 B = 1 . Answer. a n = 4 n + ( − 3 ) n a_n = 4^n + (-3)^n a n = 4 n + ( − 3 ) n . Practice with new numbers
A program to try The program checks three answers by listing every case.
Read it first. Then run it. Which recurrence does each count follow?
1. Change the 7 in the first part to 9. Predict the new count from the Fibonacci numbers first.
Mistakes to avoid Overlapping cases in the split. Wrong starting values , such as w 2 = 1 w_2 = 1 w 2 = 1 for steps of 1 1 1 or 2 2 2 . A r n + B s n Ar^n + Bs^n A r n + B s n with a double root. n ! − 1 n! - 1 n ! − 1 in place of D n D_n D n . C n C_n C n for an n n n -gon. An n n n -gon has C n − 2 C_{n-2} C n − 2 triangulations. Check yourself How many moves does the Tower of Hanoi need for 6 6 6 discs? Stuck? Show a hint Show the answerSolve a n = 5 a n − 1 − 4 a n − 2 a_n = 5a_{n-1} - 4a_{n-2} a n = 5 a n − 1 − 4 a n − 2 with a 0 = 2 a_0 = 2 a 0 = 2 and a 1 = 5 a_1 = 5 a 1 = 5 . Stuck? Show a hint Show the answerFind D 5 D_5 D 5 . Stuck? Show a hint Show the answerHow many balanced strings of 3 3 3 pairs of brackets are there? Stuck? Show a hint Show the answerSolve a n = 4 a n − 1 − 4 a n − 2 a_n = 4a_{n-1} - 4a_{n-2} a n = 4 a n − 1 − 4 a n − 2 with a 0 = 3 a_0 = 3 a 0 = 3 and a 1 = 8 a_1 = 8 a 1 = 8 . Stuck? Show a hint Show the answerSources R. A. Brualdi, Introductory Combinatorics , Chapters 6, 7 and 8. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics , Chapters 1 and 6.