Massachusetts Institute of Technology Handout 17 6.042J/18.062J: Mathematics for Computer Science September 25, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 2 Solutions

Problem 1. Use induction to prove that the following equation holds for all n ≥ 2.

(1 − \frac{1}{2}) (1 − \frac{1}{3}) ⋯ (1 − \frac{1}{n}) = \frac{1}{n}

Proof. The proof is by induction on n. Let P (n) be the proposition that the above equation holds. In the base case, P (2) is true because (1 − \frac{1}{2}) = \frac{1}{2}. In the inductive step, for n ≥ 2 assume P (n) to prove P (n + 1) as follows.

(1 − \frac{1}{2}) (1 − \frac{1}{3}) ⋯ (1 − \frac{1}{n}) (1 − \frac{1}{n + 1}) = \frac{1}{n} (1 − \frac{1}{n + 1})
= \frac{1}{n} · \frac{n}{n + 1}
= \frac{1}{n + 1}

The first step uses the induction hypothesis, and the second and third steps are simplifications. This shows that P (n) implies P (n + 1), and the claim is proved by induction.

Problem 2. Use induction to prove that the following equation holds for all n ≥ 1.

\frac{1}{2^{1}} + \frac{1}{2^{2}} + \frac{1}{2^{3}} + … \frac{1}{2^{n}} = 1 − \frac{1}{2^{n}}

Proof. The proof is by induction. Let P (n) be the proposition that the above equation holds. In the base case, P (1) is true because \frac{1}{2^{1}} = 1 − \frac{1}{2^{1}} . In the inductive step, for n ≥ 1 assume P (n) to prove P (n + 1) as shown below.

\frac{1}{2^{1}} + \frac{1}{2^{2}} + \frac{1}{2^{3}} + … \frac{1}{2^{n}} + \frac{1}{2^{n+1}} = (1 − \frac{1}{2^{n}} ) + \frac{1}{2^{n+1}}
= 1 − \frac{1}{2^{n+1}}

The first step uses the induction hypothesis, and the second step is simplification. This shows that P (n) implies P (n + 1), and the claim is proved by induction.

Problem 3. Use induction on n to prove that the following inequality holds for all integers n ≥ 1 and for all non-negative real numbers x_{1}, …, x_{n}.

(x_{1} + x_{2} + … + x_{n})^{2} ≥ x_{1}^{2} + x_{2}^{2} + … + x_{n}^{2}

Proof. The proof is by induction on n. Let P (n) be the proposition that the above inequality holds for all non-negative real numbers x_{1}, …, x_{n}. In the base case, P (1) is true because both sides of the inequality are equal to x_{1}^{2}, and so the ≤ relation is satisfied. In the inductive step, for n ≥ 1 assume P (n) in order to prove P (n + 1) as shown below.

(x_{1} + x_{2} + … + x_{n} + x_{n+1})^{2} = (x_{1} + x_{2} + … + x_{n})^{2} + 2(x_{1} + x_{2} + … + x_{n})x_{n+1} + x_{n+1}^{2}
≥ (x_{1} + x_{2} + … + x_{n})^{2} + x_{n+1}^{2}
≥ x_{1}^{2} + x_{2}^{2} + … + x_{n}^{2} + x_{n+1}^{2}

The first step is algebra. In the second step, a term is dropped; this gives an inequality, because the dropped term must be non-negative on account of all the x_{i} being non-negative. The third step uses the induction hypothesis. This shows that P (n) implies P (n + 1), and the claim is proved by induction.

Problem 4. Use induction to prove that for all n ≥ 2, the quantity n(n^{2} − 1)(n^{2} − 4) is either divisible by 5 or by 7. For example, 6(6^{2} − 1)(6^{2} − 4) = 6720 = 7 · 960.

An induction proof with the hypothesis that the expression is divisible by 5 or by 7 will not go through; this assumption is not strong enough to complete the inductive step. In fact, the expression is always divisible by 5, but is only sometimes divisible by 7. Therefore, the right idea is to strengthen the induction hypothesis to assert that the expression is always divisble by 5.

Proof. We will prove the stronger statement that n(n^{2} −1)(n^{2} −4) is always divisible by 5. The proof uses the fact that this expression can be rewritten by factoring n^{2} − 1 and n^{2} − 4 as follows:

n(n^{2} − 1)(n^{2} − 4) = (n − 2)(n − 1)n(n + 1)(n + 2).

The proof now proceeds by induction. Let P (n) be the propositon that (n−2)(n−1)n(n+ 1)(n + 2) is divisible by 5. In the base case, P (5) is true because 5(5^{2} − 1)(5^{2} − 4) = 2520 = 5 · 504. In the inductive step, for n ≥ 2 assume P (n) to prove P (n + 1); that is, we want to prove that (n − 1)n(n + 1)(n + 2)(n + 3) is divisible by 5. We can rewrite this expression as follows.

(n − 1)n(n + 1)(n + 2)(n + 3) = (n − 2)(n − 1)n(n + 1)(n + 2) +
5(n − 1)n(n + 1)(n + 2)

The top term on the right is divisible by 5 by the induction hypothesis, and the botton term on the right is divisible by 5 because the leading coefficient is 5. Therefore, the right side and the left side of the equation are both divisible by 5. This shows that P (n) implies P (n + 1), and the claim is proved by induction.

Problem 5. Use induction on n to prove that for all n ≥ 0, there are 2n^{2} +2n+1 solutions to the inequality |x| + |y| ≤ n, where x and y are integers.

Proof. The proof is by induction on n. Let P (n) be the proposition that there are 2n^{2} + 2n + 1 solutions to the inequality |x| + |y| ≤ n, where x and y are integers. In the base case, P (0) is true because 2(0)^{2} + 2(0) + 1 = 1, and there is one solution to the equation |x| + |y| ≤ 0, namely x = y = 0.

In the inductive step, assume P (n) to prove P (n + 1). That is, we want to prove that there are 2(n + 1)^{2} + 2(n + 1) + 1 = 2n^{2} + 6n + 5 solutions to the inequality |x| + |y| ≤ n + 1. Every solution to this inequality is also either a solution to the tighter inequality |x|+|y| ≤ n or else to the equation |x|+|y| = n+1. Thus, the number of solutions is equal to the number of solutions to the tighter inequality plus the number of solutions to the equation.

By induction, there are 2n^{2} +2n+1 solutions to the tighter inequality. All that remains is to count solutions to the equation. The value of x must be in the range −(n + 1), …, n + 1. If x takes on either of the two values −(n + 1) or n + 1, then there is a single solution, with y = 0. If x takes on one of the 2n + 1 values in the range −n, …, n, then there are two solutions, one with y = n + 1 − |x| and one with y = −(n + 1 − |x|). Thus, there are 2 + 2 · (2n + 1) = 4n + 4 solutions to the equation and 2n^{2} + 2n + 1 solutions to the tighter inequality, giving 2n^{2} + 6n + 5 solutions in all, as desired. Therefore, P (n) implies P (n + 1), and the claim is proved by induction.

Problem 6. The 6.042 mascot, Theory Pig, made a startling discovery while playing with his prized collection of unit squares over the weekend. Here is what happened.

First, Theory Pig put his favorite unit square down on the floor as in diagram (a) of Figure 1. He noted that the length of the periphery of the resulting shape was 4, an even number. Next, he put a second unit square down next to the first so that the two squares shared an edge as in diagram (b). He noticed that the length of the periphery of the resulting shape was now 6, which is also an even number. (The periphery of each shape in the figure is indicated by a thicker line.) Theory Pig continued to place squares so that each new square shared an edge with at least one previously-placed square and no squares overlapped. Eventually, he arrived at the shape in diagram (c). He realized that the length of the periphery of this shape was 36, which is again an even number.

Our plucky porcine pal is perplexed by this peculiar pattern. Use induction on the number of squares to prove that periphery length is always even, no matter how many squares Theory Pig places or how he arranges them.

Figure 1: Some shapes that Theory Pig created.

Proof. The proof is by induction. Let P (n) be the proposition that the periphery length is even after n squares are placed. In the base case, P (1) is true because the periphery of a single square has length 4, which is even.

In the inductive step, assume that the periphery length is even after n squares are placed to prove that the periphery length is even after n + 1 squares are placed. The (n + 1)-st square could share 1, 2, 3, or 4 edges with previously-placed squares.

• If the new square shares 1 edge with a previously placed square, then this one edge is removed from the periphery, but three edges of the new square are added to the periphery. Overall, the periphery length increases by two and thus remains even.

• If the new square shares 2 edges with previously placed squares, then these two edges are removed from the periphery, but two edges of the new square are added. The periphery length is unchanged and thus remains even.

• If the new square shares 3 edges, then these three edges are removed from the periphery, but one edge is added. The periphery length decreases by two and remains even.

• If the new square shares 4 edges, then these four edges are removed from the periphery and none are added. The periphery length decreases by four and remains even.

In all cases, the length of the periphery remains even. Therefore, for all n ≥ 1, P (n) implies P (n + 1) and the claim is proved by induction.

Problem 7. The 6.042 course information sheet states:

During the second hour or so [of recitation], the students will work in groups of three or four, and each group will be assigned a problem to solve as a team.

Using strong induction, prove that if a recitation contains at least 6 students, then the class can be divided into teams, each consisting of either 3 or 4 students.

Proof. The proof is by strong induction. Let P (n) be the proposition that a recitation with n students can be divided into teams of 3 or 4. In the base cases, P (6) is true because there could be two teams of 3, P (7) is true because there could be a team of 3 and a team of 4, and P (8) is true because there could be two teams of 4. In the inductive step, for n ≥ 8, assume P (6), …, P (n) to prove P (n + 1). If a recitation has n + 1 students, then three students can form a team of 3, and the remaining n − 2 students can be divided into teams of 3 or 4 by induction. This shows that P (6), …, P (n) imply P (n + 1), and the claim is proved by induction.

Problem 8. Suppose that the sequence x_{1}, x_{2}, x_{3}, … is defined as follows. The first term, x_{1}, is equal to 1. For n ≥ 1, the term x_{n+1} is equal to x_{n} if n + 1 is odd and is equal to 1+x_{(n+1)/2} if n+1 is even. Use strong induction on n to prove that for all n ≥ 1, the number of digits in the binary representation of n is equal to x_{n}.

Proof. The proof is by strong induction. Let P (n) be the proposition there are x_{n} digits in the binary representation of n. In the base case, P (1) is true because there is a single digit in the binary representation of 1. In the inductive step, for n ≥ 1, assume P (1), …, P (n) to prove P (n + 1). There are two cases to consider.

1. If n + 1 is odd, then the binary representation of n + 1 is the binary representation of n with the least significant digit changed from a zero to a one. By the induction hypothesis, there are x_{n} digits in the binary representation of n. Therefore, there also are x_{n} = x_{n+1} digits in the binary representation of n + 1.

2. If n + 1 is even, then the binary representation of n + 1 is the binary representation of (n + 1)/2 with a zero appended. By the induction hypothesis, there are x_{(n+1)/2} digits in the binary representation of (n+1)/2. Therefore, there are 1+x_{(n+1)/2} = x_{n+1} digits in the binary representation of n + 1.

This shows that P (1), …, P (n) imply P (n + 1), and the claim is proved by induction.

Problem 9. Suppose that x_{0} = 0, x_{1} = \frac{1}{2}, and the following equation holds for all n ≥ 1:

x_{n+1} + x_{n−1} = \sqrt{3}x_{n}

Use strong induction to prove that x_{n} = sin(\frac{nπ}{6}) for all n ≥ 0.

Proof. The proof will make use of the trignometric identity for a sum of sines,

sin A + sin B = 2 cos \frac{A − B}{2} sin \frac{A + B}{2} .

In particular, the following form of the identity will be needed:

sin A = 2 cos \frac{A − B}{2} sin \frac{A + B}{2} − sin B

The proof is by strong induction. Let P (n) be the proposition that x_{n} = sin \frac{nπ}{6}. In the base cases, P (0) is true because x_{0} = 0 = sin 0, and P (1) is true because x_{1} = \frac{1}{2} = sin \frac{π}{6}. In the inductive step, for n ≥ 1 assume P (0), …, P (n) to prove P (n + 1). That is, we want to prove that x_{n+1} = sin \frac{(n+1)π}{6}. The equation stated in the problem can be rewritten as follows:

x_{n+1} = \sqrt{3}x_{n} − x_{n−1}
= \sqrt{3} sin \frac{nπ}{6} − sin \frac{(n − 1)π}{6}
= sin \frac{(n + 1)π}{6}

The second equation follows from the induction hypothesis, and the third equation follows from the sum-of-sines identity with A = \frac{(n+1)π}{6} and B = \frac{(n−1)π}{6}. Therefore, P (0), …, P (n) imply P (n + 1), and the claim is proved by strong induction.

Problem 10. There are two types of creature on planet Xoros 19, A-lings and B-lings. Furthermore, every creature belongs to a particular generation. The creatures in each generation reproduce according to certain rules and then die off. The subsequent generation consists entirely of their offspring.

The creatures of Xoros 19 pair with a mate in order to reproduce. First, as many A-B pairs as possible are formed. The remaining creatures form A-A pairs or B-B pairs, depending on whether there is an excess of A-lings or of B-lings. If there are an odd number of creatures, then one in the majority species dies without reproducing. The number and type of offspring is determined by the types of the parents

• If both parents are A-lings, then they have three A-ling offspring.

• If both parents are B-lings, then they have two B-ling offspring and one A-ling offspring.

• If there is one parent of each type, then they have one offspring of each type.

There are 200 A-lings and 800 B-lings in the first generation. Use induction to prove that the number of A-lings will always be at most twice the number of B-lings.

An induction proof with the hypothesis that the number of A-lings is always at most twice the number of B-lings will not go through. A stronger induction hypothesis is required.

Proof. We will prove that there are always at least as many B-lings as A-lings; the claim that the number of A-lings is always at most twice the number of B-lings is weaker and thus follows.

The proof is by induction on the generation number. Let P (n) be the proposition that there are at least as many B-lings as A-lings in generation n. In the base case, P (1) is true because there are 800 B-lings and only 200 A-lings in the first generation.

In the inductive step, for n ≥ 1 assume that there are at least as many B-lings as A-lings in generation n to prove that there are at least as many B-lings as A-lings in generation n + 1. Let a be the number of A-lings in generation n, and let b be the number of B-lings. Note that b ≥ a by the induction assumption. Then there are no A-A pairs formed, there are a A-B pairs formed, and there are ⌊\frac{b−a}{2}⌋ B − B pairs formed. As a result, the number of A-lings in generation n + 1 is a + ⌊\frac{b−a}{2}⌋, and the number of B-lings is a + 2⌊\frac{b−a}{2}⌋. Therefore, there are at least as many B-lings as A-lings in generation n + 1. Thus, for all n ≥ 1, P (n) implies P (n + 1), and the claim is proved by induction.