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

Problem Set 2

Due: Start of class on September 22, 1998.

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}

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}}

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}

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.

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.

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.

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.

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}.

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.

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.