A brief note on Strong Induction, Inequalities and Recursion . Read it before a test. Try each question at the end before you open its answer.
Inequalities Base case where it starts: 2 n > n 2 2^n > n^2 2 n > n 2 only from n = 5 n = 5 n = 5 ; n ! > 2 n n! > 2^n n ! > 2 n from n = 4 n = 4 n = 4 . Step: compare the next terms, then prove the extra fact, such as 2 k 2 ≥ ( k + 1 ) 2 2k^2 \ge (k + 1)^2 2 k 2 ≥ ( k + 1 ) 2 for k ≥ 3 k \ge 3 k ≥ 3 . Bernoulli: ( 1 + x ) n ≥ 1 + n x (1 + x)^n \ge 1 + nx ( 1 + x ) n ≥ 1 + n x for x ≥ − 1 x \ge -1 x ≥ − 1 and n ≥ 1 n \ge 1 n ≥ 1 . Stuck step: prove a stronger statement that carries itself forward. Strong induction and well-ordering Strong induction: assume every case up to k k k , prove k + 1 k + 1 k + 1 . Base cases: a step that goes back r r r places needs r r r of them in a row. Two stamp values a a a , b b b with no common factor: the largest amount that cannot be paid is a b − a − b ab - a - b ab − a − b . Well-ordering: every non-empty set of positive integers has a least element. Use it with a smallest counterexample. Recursive sequences Method: list terms, guess a formula, prove it. Linear rule: a n + 1 = r a n + c a_{n + 1} = ra_n + c a n + 1 = r a n + c gives a n = r n − 1 ( a 1 + L ) − L a_n = r^{n - 1}(a_1 + L) - L a n = r n − 1 ( a 1 + L ) − L with L = c r − 1 L = \dfrac{c}{r - 1} L = r − 1 c . Fibonacci: F 1 + ⋯ + F n = F n + 2 − 1 F_1 + \dots + F_n = F_{n + 2} - 1 F 1 + ⋯ + F n = F n + 2 − 1 , and F n + 1 F n − 1 − F n 2 = ( − 1 ) n F_{n + 1}F_{n - 1} - F_n^2 = (-1)^n F n + 1 F n − 1 − F n 2 = ( − 1 ) n . Bounded and increasing: prove each by induction, then find the limit from L = f ( L ) L = f(L) L = f ( L ) . A worked example Prove that n ! > 2 n n! > 2^n n ! > 2 n for every n ≥ 4 n \ge 4 n ≥ 4 .
Base. 4 ! = 24 > 16 4! = 24 > 16 4 ! = 24 > 16 . Step. If k ! > 2 k k! > 2^k k ! > 2 k with k ≥ 4 k \ge 4 k ≥ 4 , then ( k + 1 ) ! = ( k + 1 ) k ! > 2 × 2 k = 2 k + 1 (k + 1)! = (k + 1)k! > 2 \times 2^k = 2^{k + 1} ( k + 1 )! = ( k + 1 ) k ! > 2 × 2 k = 2 k + 1 . Conclusion. By induction, n ! > 2 n n! > 2^n n ! > 2 n for every n ≥ 4 n \ge 4 n ≥ 4 . Practice with new numbers
A program to try The program tests three results of this note for many values of n n n .
Read it first. Then run it. Do all three lines say True?
1. Change the range of the first test to start at n = 2 n = 2 n = 2 . What happens, and why?
Mistakes to avoid Base case at 1 1 1 when the result starts later. One base case for a step that goes back two or more places. Multiplying an inequality by a number that may be negative. Assuming a limit before showing the sequence is bounded and increasing. Check yourself Find the smallest n n n with 2 n > n 2 2^n > n^2 2 n > n 2 for every later n n n as well. Stuck? Show a hint Show the answerGive the Bernoulli lower bound for 1.05 8 1.05^{8} 1.0 5 8 . Stuck? Show a hint Show the answerStamps come in 3 3 3 and 7 7 7 units. What is the largest amount that cannot be paid? Stuck? Show a hint Show the answerFind a 6 a_6 a 6 for a 1 = 1 a_1 = 1 a 1 = 1 and a n + 1 = 2 a n + 1 a_{n + 1} = 2a_n + 1 a n + 1 = 2 a n + 1 . Stuck? Show a hint Show the answerSources Arthur Engel, Problem-Solving Strategies , Chapter 8. Richard Hammack, Book of Proof , Chapter 10.