InductionTal SuttonSeptember 18, 2006Induction. Let P (x) be a statement about x. In order to show that P (n) is(eventually) true for all possible integers n greater than some starting point, a, onecan proceed as follows:• (The “first” case) Show there is some integer a such that P (a) is true.• (The Inductive Hypothesis) Assume the statement is true for integers up tok ≥ a (on down to the first case P (a)).• (The Inductive Step) Prove that the “next” case, P (k + 1), is true using thefirst case and the Inductive Hypothesis.Example 1. Prove for all n ≥ 112+ 22+ . . . + n2=n(n + 1)(2n + 1)6.Example 2. If V, E, and F represent (respectively) the number of vertices, edges,and faces of a connected planar graph, thenV − E + F = 2.Example 3. Use induction to show that for all n ≥ 0 thatn55+n42+n33−n30∈ Z.Example 4 (Recurrence). A (fair) coin is tossed n times. What is the probabilitythat two heads appear in succession somewhere in the sequence of throws?Example 5 (General Induction). Let Fkdenote the kth Fibonacci number,proveF2n+1+ F2n= F2n+1.Problem 1. If {an} is a sequence such that for n ≥ 1, (2 − an)an+1= 1, whathappens to anas n tends towards infinity?Problem 2. Use induction to prove that there are exactly 2nsubsets of a setcontaining n elements.Problem 3. Show that every number in the following sequence is divisible by53:1007, 10017, 100117, 1001117, . . . .Problem 4. Suppose n coins are given, named C1, C2, . . ., Cn. For each k, Ckisbiased so that, when tossed, it has probability12k+1of falling heads. If then coins are tossed, what is the probability that the number of heads is odd?Express the answer as a rational function of n. (Putnam 2001).Problem 5. Let r be a number such that r +1ris an integer. Prove that rn+1rnis an integer for every positive integer n.Problem 6. Let a1, a2, . . ., anbe a permutation of the set Sn= {1, 2, . . . , n}.An element i in Snis called a fixed point of this permutation if ai= i.1. A derangement of Snis a permutation of Snhaving no fixed points.Let gndenote the number of derangements of Sn. Show thatg1= 0, g2= 1,andgn= (n − 1)(gn−2+ gn−1) for n > 2.2. Let fnbe the number of permutations of Snwith exactly 1 fixed point.Show that|fn− gn| = 1.Problem 7. Let Pndenote the number of regions formed when n lines are drawnin the Euclidean plane in such a way that no three lines meet at one pointand no two lines are parallel. Come up with a recurrence relation for Pn,and prove that it holds for all n ≥ 1.Problem 8. Prove the arithmetic-mean-geometric-mean inequality, which states,for a1, . . ., anall positive real numbers, thata1+ . . . + ann≥ (a1· . . . · an)1n.Problem 9. Let n be a positive integer, and ai≥ 1, for i = 1, 2, . . . , n. Showthat(1 + a1)(1 + a2) ···(1 + an) ≥2nn + 1(1 + a1+ . . . + an).Problem 10. Let Fkbe the kth Fibonacci number, prove for all positive integersthatFn=1√5 1 +√52!n− 1 −√52!n!.Problem 11. Suppose a1, . . ., anand b1, . . ., bnare real numbers, provenXk=1qa2k+ b2k≥vuut nXk=1ak!2+ nXk=1bk!2.Problem 12. Show that for n ≥ 6 a square can be dissected into n smallersquares, not necessarily all of the same