91Ó°ÊÓ

Prove that if a statement can be proved by the well-ordering principle, then it can be proved by ordinary mathematical induction.

You have two parents, four grandparents, eight greatgrandparents, and so forth. a. If all your ancestors were distinct, what would be the total number of your ancestors for the past 40 generations (counting your parents' generation as number one)? (Hint: Use the formula for the sum of a geometric sequence.) b. Assuming that each generation represents 25 years, how long is 40 generations? c. The total number of people who have ever lived is approximately 10 billion, which equals \(10^{10}\) people. Compare this fact with the answer to part (a). What do you deduce?

An L-tromino, or tromino for short, is similar to a domino but is shaped like an L: th. Call a checkerboard that is formed using \(m\) squares on a side an \(m \times m\) checkerboard. If one square is removed from a \(4 \times 4\) checkerboard, the remaining squares can be completely covered by trominos. For instance, a covering for one such board is the following: Use mathematical induction to prove that for any integer \(n \geq 1\), if one square is removed from a \(2^{n} \times 2^{n}\) checkerboard, the remaining squares can be completely covered by trominos.

Use Theorem \(4.2 .2\) to prove that if \(m\) is any odd integer and \(n\) is any integer, then \(\sum_{k=0}^{m-1}(n+k)\) is divisible by \(m\). Does the conclusion hold if \(m\) is even? Justify your answer.

In a round-robin tournament each team plays every other team exactly once. If the teams are labeled \(T_{1}, T_{2}, \ldots, T_{n}\), then the outcome of such a tournament can be represented by a drawing, called a directed graph, in which the teams are represented as dots and an arrow is drawn from one dot to another if, and only if, the team represented by the first dot beats the team represented by the second dot. For example, the directed graph below shows one outcome of a round-robin tournament involving five teams, \(\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}\), and \(\mathbf{E}\). Use mathematical induction to show that in any round-robin tournament involving \(n\) teams, where \(n \geq 2\), it is possible to label the teams \(T_{1}, T_{2}, \ldots, T_{n}\) so that \(T_{i}\) beats \(T_{i+1}\) for all \(i=\) \(1,2, \ldots, n-1\). (For instance, one such labeling in the example above is \(T_{1}=A, T_{2}=B, T_{3}=C, T_{4}=E, T_{5}=D\). (Hint: Given \(k+1\) teams, pick one-say \(T^{\prime}\)-and apply the inductive hypothesis to the remaining teams to obtain an ordering \(T_{1}, T_{2}, \ldots, T_{k}\). Consider three cases: \(T^{\prime}\) beats \(T_{1}, T\) loses to the first \(m\) teams (where \(1 \leq m \leq k-1\) ) and beats the \((m+1)\) st team, and \(T^{\prime}\) loses to all the other teams.)

On the outside rim of a circular disk the integers from 1 through 30 are painted in random order. Show that no matter what this order is, there must be three successive integers whose sum is at least 45 .

a. Prove that \(n !+2\) is divisible by 2 , for all integers \(n \geq 2\). b. Prove that \(n !+k\) is divisible by \(k\), for all integers \(n \geq 2\) and \(k=2,3, \ldots, n\). c. Given any integer \(m \geq 2\), is it possible to find a sequence of \(m-1\) consecutive positive integers none of which is prime? Explain your answer.

Write each of \(58-60\) as a single summation or product. $$ 2 \cdot \sum_{k=1}^{n}\left(3 k^{2}+4\right)+5 \cdot \sum_{k=1}^{n}\left(2 k^{2}-1\right) $$

Use repeated division by 2 to convert (by hand) the integers in \(63-65\) from base 10 to base 2 . $$ 90 $$

Use repeated division by 2 to convert (by hand) the integers in \(63-65\) from base 10 to base 2 . $$ 205 $$