InductionKsenija Simic-Muller and Matt OndrusFeb 28, 2007Example 1. Every positive integer n can be expressed as n = c0+ c121+ c222+ ···+ cM2Mfor some M ≥ 0, where ci∈ {0, 1} for all i.Example 2. (Note: This is an example of a wrong proof.)Suppose that S : Z≥1→ Z is a function with the property that S(n) = 5S(n−1)−6S(n−2),where S(1) = 9 and S(2) = 20. Prove that S(n) = 3 · 2n+ 3n.Example 3. Suppose you are given a square checkerboard with side-length 2nand with onemissing square. Prove that the remaining squares on the board can be tiled with trominos.Note that a tromino is an objec t shaped like .Problem 1. A winning configuration in the game of MiniTetris is a complete tiling of a2 × n board using only the three shapes shown below:, ,Prove that the number of winning configurations on a 2 ×n MiniTetris board (n ≥ 1) isTn= (2n+1+ (−1)n)/3.Problem 2. We are given a chocolate bar with m ×n squares of chocolate, and our task isto divide it into mn individual squares. We are only allowed to split one piece of chocolateat a time using a vertical or a horizontal break. For example, suppose that the chocolatebar is 2 × 2. The first split makes two pieces, both 2 × 1. Each of thes e pieces requires onemore split to form single squares. This gives a total of three splits.Use strong induction to conclude the following: Theorem. To divide up a chocolate bar withm × n squares, we need mn − 1 splits.Problem 3. You begin with a stack of n boxes. Then you make a sequence of moves. Ineach move, you divide one stack of boxes into two nonempty stacks. The game ends whenyou have n stacks, each containing a single box. You earn points for each move; in particular,if you divide one stack of height a + b into two stacks with heights a and b, then you scoreab points for that move. Your overall score is the sum of the points that you earn for eachmove. What strategy should you use to maximize your total score?Problem 4. Prove that consecutive Fibonacci numbers are always relatively prime.Problem 5. Show that every positive integer can be expressed uniquely as the sum ofdistinct, non-consecutive Fibonacci numbers (here, non-consecutive means that no two ofthe Fibonacci numbers in the sum are consecutive Fib onacci numbers).Problem 6. Let n = 2k. Prove that we can select n integers from any (2n − 1) integerssuch that their sum is divisible by n.Problem 7. Prove that if you triangulate a convex n-gon, then there are at least twovertices of degree two. Note: Think of a convex n -gon as a graph consisting of n verticesand n-edges arranged in a cycle. To triangulate an n-gon is to join non-adjacent verticeswith edges in such a way that no edges cross each other and all of the resulting faces aretriangles.Problem 8. Let S(n) denote the number of strings of length n built f rom the alphabet{H, T } that do not contain the substring HH. Prove thatS(n) = 5 + 3√510! 1 +√52!n+ 5 − 3√510! 1 −√52!n.Problem 9. Prove that the faces of a planar graph can be colored with two colors (so thatno two adjacent faces are the same color) iff all of its vertices have even degree.Problem 10. In an m×n matrix of real numbers, we mark at least p of the largest numbers(p ≤ m) in every column, and at least q of the largest numbers (q ≤ n) in every row. Provethat at least pq numbers are marked twice.Problem 11. (Putnam, 1972) Show that, for all n > 1, n does not divide 2n− 1.Problem 12. There are no positive integer solutions of x4+ y4= z2.Hint: You need to know that every positive integer solution of a2+ b2= c2where a, b, andc are relatively prime can be expressed in terms of two relatively prime numbers m, and nwhere a = m2− n2, b = 2mn, and c = m2+