6.042/18.] Mathematics for Computer Science February 11, 2005 Srini devadas and Eric Lehman Notes for recitation 4 1 Strong Induction Recall the principle of strong induction Principle of Strong Induction. Let P(n)be a predicate. If ·P(0) is true,an for all n∈NP(O)∧P(1).…AP(m) implies F(n+1), then P(n) is true for all nE N As an example, lets derive the fundamental theorem of arithmetic Theorem 1. Every positive integer n >2 can be written as the product of primes Proof. The proof is by strong induction. Let P(n) be the statement that n can be written as the product of primes Base case: 2 is itself a prime, so P(2)hold Inductive case: We show that P(2)A P(3).P(n)= P(n +1)is true. Assume that P(2), P(3),.P(n)are true. Consider n +1. If n+ l is a prime number, P(n +1)holds Otherwise, n+ 1 is a composite number; thus it has factors 2 2
� � � � 6.042/18.062J Mathematics for Computer Science February 11, 2005 Srini Devadas and Eric Lehman Notes for Recitation 4 1 Strong Induction Recall the principle of strong induction: Principle of Strong Induction. Let P(n) be a predicate. If • P(0) is true, and • for all n ∈ N, P(0) ∧ P(1). . . ∧ P(n) implies P(n + 1), then P(n) is true for all n ∈ N. As an example, let’s derive the fundamental theorem of arithmetic. Theorem 1. Every positive integer n ≥ 2 can be written as the product of primes. Proof. The proof is by strong induction. Let P(n) be the statement that n can be written as the product of primes. Base case: 2 is itself a prime, so P(2) holds. Inductive case: We show that P(2) ∧ P(3). . . P(n) ⇒ P(n + 1) is true. Assume that P(2), P(3), . . . P(n) are true. Consider n + 1. If n + 1 is a prime number, P(n + 1) holds. Otherwise, n + 1 is a composite number; thus it has factors 2 ≤ u, v < n + 1 such that u v = n + 1. By the inductive hypothesis, u = i pi for primes pi and v = j · pj for primes pj , so therefore, n + 1 = i pi pj · , i.e. P(n + 1) is true. By the principle of strong induction, P(n) is true for all n ≥ 2
Recitation 4 2 Problem: Mini-Tetris A winning configuration in the game of Mini-Tetris is a complete tiling of a 2 x n board using only the three shapes shown below For example, here are several possible winning configurations on a 2 x 5 board 1. Let Tn denote the number of different winning configurations on a 2 x n board deter mine the values of Ti, 12, and T3 Solution. Ti=1, T2=3, and T3=5 2. Express Tn in terms of Tn-1 and Tn-2 Solution. Every winning configuration on a 2 x n board is of one of the following three types 8 There are In-1 winning configurations of the first type, and there are Tn-2 winning con- figurations of the second and third types. Overall, the number of winning configurations ona2× n board is:
Recitation 4 2 2 Problem: MiniTetris A winning configuration in the game of MiniTetris is a complete tiling of a 2 × n board using only the three shapes shown below: For example, here are several possible winning configurations on a 2 × 5 board: 1. Let Tn denote the number of different winning configurations on a 2 × n board. Determine the values of T1, T2, and T3. Solution. T1 = 1, T2 = 3, and T3 = 5. 2. Express Tn in terms of Tn−1 and Tn−2. Solution. Every winning configuration on a 2×n board is of one of the following three types: 2 x (n−1) configuration 2 x (n−2) configuration 2 x (n−2) configuration There are Tn−1 winning configurations of the first type, and there are Tn−2 winning con figurations of the second and third types. Overall, the number of winning configurations on a 2 × n board is: Tn = Tn−1 + 2Tn−2
Recitation 4 3. Using strong induction, prove that the number of winning configurations on a 2 x n Mini-Tetris board(n 1)is T Solution. The proof is by strong induction on n, with the induction hypothesis Tn (2++(1))/3. The hypothesis is true for n=l and n= 2, since we determined above that T1=1=(21+1+(-1)2)/3andT2=3=(22+1+(-1))/3. Now suppose n >2 and assume that the hypothesis holds for all k1
Recitation 4 3 3. Using strong induction, prove that the number of winning configurations on a 2 × n MiniTetris board (n ≥ 1) is: n 2n+1 + (−1) Tn = 3 Solution. The proof is by strong induction on n, with the induction hypothesis Tn = (2n+1 + (−1)n)/3. The hypothesis is true for n = 1 and n = 2, since we determined above 1+1 + (−1) that T1 = 1 = (2 2+1 + (−1) 1)/3 and T2 = 3 = (2 2)/3. Now suppose n ≥ 2 and assume that the hypothesis holds for all k < n. Starting from the equation derived in the preceding problem part, we have: Tn = = Tn−1 + 2Tn−2 2n + (−1)n−1 3 + 2 · 2n−1 + (−1)n−2 3 = 2n − (−1)n + 2n + 2(−1)n 3 3 = 2n+1 + (−1)n 3 We use the induction hypothesis twice in the second step, and then simplify in the third and fourth steps. This completes the inductive step. By strong induction, the hypothesis holds for all n ≥ 1
Recitation 4 3 Problem: Breaking a chocolate bar We are given a chocolate bar with m x n squares of chocolate, and our task is to divide it into mn individual squares. We are only allowed to split one piece of chocolate at a time using a vertical or a horizontal break For example, suppose that the chocolate bar is 2 x 2. The first split makes two pieces both 2 x 1. Each of these pieces requires one more 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 with m x n squares, we need at most mn-1 splits Solution. This theorem does not immediately lend itself to an induction proof, since there are two variables. In general, propositions involving several natural-valued vari ables can often be proved by using a sort of nested induction. However, in this case, we can get by with a single-variable induction and a trick Intuitively, to break up a big chocolate bar, we need one split to make two pieces, and then we can break up the two pieces recursively. This suggests a proof using strong in duction on the size of the chocolate bar, where size is measured in chocolate squares. Now instead of a problem involving two variables(the two dimensions), we have a problem in one variable(the size). With this simplification, we can prove the theorem using strong induction Proof. The proof is by strong induction on the size of the chocolate bar. Let P(k)be the proposition that a chocolate bar of size k requires at most k-1 splits Base case, k= 1: P(1)is true because there is only a single square of chocolate, and 1=0 splits are required Induction step: We suppose k> 1 and any chocolate bar of size s, where 1<s< k, requires at most s-1 splits. We must now show there is a way to split a chocolate bar of size k+ l with at most k splits To do this, first break the chocolate bar of size k+l into two smaller pieces of size p and q where p+q=k+1. This is certainly possible because the size of the bar is at least two Now the pieces of sizes p and g are between one and k, so by strong induction, breaking these two pieces into single squares requires only p-l and q-1 splits, respectiv total number of splits required to break the bar of size k l into single squares is therefore at most1+(P-1)+(q-1)=p+q-1=(k+1)-1 This shows that P()implies P(k+1), and the claim is proved by strong induction. O
Recitation 4 4 3 Problem: Breaking a chocolate bar We are given a chocolate bar with m × n squares of chocolate, and our task is to divide it into mn individual squares. We are only allowed to split one piece of chocolate at a time using a vertical or a horizontal break. For example, suppose that the chocolate bar is 2 × 2. The first split makes two pieces, both 2 × 1. Each of these pieces requires one more 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 with m × n squares, we need at most mn − 1 splits. Solution. This theorem does not immediately lend itself to an induction proof, since there are two variables. In general, propositions involving several naturalvalued variables can often be proved by using a sort of nested induction. However, in this case, we can get by with a singlevariable induction and a trick. Intuitively, to break up a big chocolate bar, we need one split to make two pieces, and then we can break up the two pieces recursively. This suggests a proof using strong induction on the size of the chocolate bar, where size is measured in chocolate squares. Now instead of a problem involving two variables (the two dimensions), we have a problem in one variable (the size). With this simplification, we can prove the theorem using strong induction. Proof. The proof is by strong induction on the size of the chocolate bar. Let P(k) be the proposition that a chocolate bar of size k requires at most k − 1 splits. Base case, k = 1: P(1) is true because there is only a single square of chocolate, and 1 − 1 = 0 splits are required. Induction step: We suppose k ≥ 1 and any chocolate bar of size s, where 1 ≤ s ≤ k, requires at most s − 1 splits. We must now show there is a way to split a chocolate bar of size k + 1 with at most k splits. To do this, first break the chocolate bar of size k+1 into two smaller pieces of size p and q where p + q = k + 1. This is certainly possible because the size of the bar is at least two. Now the pieces of sizes p and q are between one and k, so by strong induction, breaking these two pieces into single squares requires only p − 1 and q − 1 splits, respectively. The total number of splits required to break the bar of size k+1 into single squares is therefore at most 1 + (p − 1) + (q − 1) = p + q − 1 = (k + 1) − 1 = k. This shows that P(k) implies P(k+1), and the claim is proved by strong induction
Recitation 4 4 Problem: fibonacci numbers The Fibonacci numbers are defined as follows Fi= l, F2= l, and for all k> 3, Fk= Fk-1+ Fk-2 The first few terms of the Fibonacci sequence are 1,1,2,3,5,8,13,21, We cant find every single number in the Fibonacci sequence-for instance, 4 is not a number in the sequence. But can we express every n> 1 as the sum of distinct terms in the Fibonacci sequence? Indeed, we can Use strong induction to prove the following Theorem 2. Every n 2 1 can be expressed as the sum of distinct terms in the Fibonacci sequence Solution Proof. We proceed by strong induction. Let P(n)be the statement that n can be written as the sum of distinct terms in the Fibonacci sequence Base case: 1 itself is a term in the Fibonacci sequence, so P(1)is true nductive case: We want to show that P(1)AP(2).P(n)=>P(n+1)is true. Assume that P(1), P(2)... P(n)all hold. Consider n + 1. If n +l is a Fibonacci number, then we are done. if not, we have. for some k>1 Fk <n+l< Fk+ This gives us the equation n+1=Fk+( F Now n+1- Fk<n+l, so by the induction hypothesis, P(n+1- Fk)is true,i.e Fi+ Fi2 Furthermore, none of the Fi, is Fk, since since n+1- Fk< Fk. Therefore, we have that P(n+1)is true, FR+Fi+ Fia By the principle of strong induction, P(n)is true for all n
Recitation 4 5 4 Problem: Fibonacci numbers The Fibonacci numbers are defined as follows: F1 = 1, F2 = 1, and for all k ≥ 3, Fk = Fk−1 + Fk−2. The first few terms of the Fibonacci sequence are: 1, 1, 2, 3, 5, 8, 13, 21, . . . We can’t find every single number in the Fibonacci sequence – for instance, 4 is not a number in the sequence. But can we express every n ≥ 1 as the sum of distinct terms in the Fibonacci sequence? Indeed, we can! Use strong induction to prove the following: Theorem 2. Every n ≥ 1 can be expressed as the sum of distinct terms in the Fibonacci sequence. Solution. Proof. We proceed by strong induction. Let P(n) be the statement that n can be written as the sum of distinct terms in the Fibonacci sequence. Base case: 1 itself is a term in the Fibonacci sequence, so P(1) is true. Inductive case: We want to show that P(1) ∧ P(2). . . P(n) ⇒ P(n + 1) is true. Assume that P(1), P(2). . . P(n) all hold. Consider n + 1. If n + 1 is a Fibonacci number, then we are done. If not, we have, for some k ≥ 1, Fk < n + 1 < Fk+1. This gives us the equation: n + 1 = Fk + (n + 1 − Fk) . Now n + 1 − Fk < n + 1, so by the induction hypothesis, P(n + 1 − Fk) is true, i.e. n + 1 − Fk = Fj1 + Fj2 + . . . . Furthermore, none of the Fji is Fk, since since n + 1 − Fk < Fk. Therefore, we have that P(n + 1) is true, i.e.: n + 1 = Fk + Fj1 + Fj2 + . . . . By the principle of strong induction, P(n) is true for all n