Skip to main content

Chapter 13 Induction

Exercises Practice Problems

1. A Formula for a Sum.

Use induction to prove that

\begin{equation*} \sum_{k=0}^{n} 2^k = 2^{n+1} -1 \end{equation*}

for all \(n \geq 0\text{.}\)

  1. Base Case: Check for \(n=0,1,2\) to make sure you believe it. You actually only need to check for \(n=0\text{.}\)

  2. Inductive Hypothesis: Write down your inductive hypothesis for \(n\text{.}\)

  3. Inductive Step: Write down what you want to SHOW for \(n+1\text{.}\) Then try to find "a copy of the size \(n\) problem" in the size \(n+1\) problem. Rearrange and use your inductive hypothesis to prove the result!

2. The Number of Edges in \(K_n\).

Use induction to prove that the complete graph \(K_n\) has \(\displaystyle{\frac{n(n-1)}{2}}\) edges.

  1. Base Case: (Check for \(n=1,2,3\) to make sure you believe it. You actually only need to check for \(n=1\text{.}\))

  2. Inductive Hypothesis: Write down your inductive hypothesis for \(n\text{.}\)

  3. Inductive Step: Write down what you want to SHOW for \(n+1\text{.}\) Then try to find "a copy of the size \(n\) problem" in the size \(n+1\) problem. Rearrange and use your inductive hypothesis to prove the result!

    Hint: You have a \(K_{n+1}\text{,}\) so start by looking at a subgraph on \(n\) of the vertices.

3. A Divisibility Problem.

Use induction to prove that \(4\) divides \((5^n -1)\) for \(n \geq 1\text{.}\)

  1. Base Case: (Check for \(n=1,2,3\) to make sure you believe it. You actually only need to check for \(n=1\text{.}\))

  2. Inductive Hypothesis: Write down your inductive hypothesis for \(n\text{.}\)

    Pro Tip: A nice way to write "4 divides \((5^n-1)\)" is the statement "\(5^n-1 = 4k\) for some \(k\text{.}\)"

  3. Inductive Step: Write down what you want to SHOW for \(n+1\text{.}\) Then try to find "a copy of the size \(n\) problem" in the size \(n+1\) problem. Rearrange and use your inductive hypothesis to prove the result!

    Hint: For this problem, the easiest thing to do is "add 0 in a smart way." Namely, add \((5^n - 5^n)\) and then rearrange.

4. Tiling with \(L\)-Shaped Triominos.

An \(L\)-shaped triomino is a \(2 \times 2\) tile with one square missing. It looks like this:

  1. Consider the following \(4 \times 4\) checkerboards with one square missing (shown in black). For each board, show that you can cover the rest of the squares using \(L\)-shaped triominoes.

  2. Now consider the following \(8 \times 8\) checkerboard with one square missing (shown in black). Show that you can cover the rest of the squares using \(L\)-shaped triominoes as follows (and shown in the right diagram below). (1) Place your first triomino in the gray squares as shown. (2) Use part (a) to fill in the four \(4 \times 4\) sub-boards.

  3. Reflect on how you solved the \(8 \times 8\) problem by turning it into four instances of \(4 \times 4\) problems. Then go back to your answers in part (a) and show how you solved each \(4 \times 4\) problem by turning it into four instances of \(2 \times 2\) problems.

  4. If I gave you a \(16 \times 16\) checkerboard with one square missing, could you cover the rest with \(L\)-shaped triominoes? How would you do it?

  5. Use induction to prove the following statement:

    For \(n \geq 1\text{,}\) any \(2^n \times 2^n\) checkerboard with one square missing can be covered by \(L\)-shaped dominoes.

    1. Base Case: What is your base case?

    2. Inductive Hypothesis: State your inductive hypothesis for \(n\text{.}\)

    3. Inductive Step: Write down what you want to SHOW for \(n+1\text{.}\) Then try to find "a copy of the size \(n\) problem" in the size \(n+1\) problem. Rearrange and use your inductive hypothesis to prove the result!

5. Nearest Neighbor Pie Fight.

Consider a pie fight between an odd number of people in which everyone throws a pie at her nearest neighbor. Assume that all pairwise distances are distinct. Prove that in such a pie fight between \(2k+1\) people with \(k \geq 1\text{,}\) there is at least one person who is not hit by a pie.

  1. Base Case: (Check for \(k=1\text{.}\)) Hint: Start by considering the two people who are the smallest distance from one another.

  2. Inductive Hypothesis: Write down your inductive hypothesis for \(n\text{.}\)

  3. Inductive Step: Write down what you want to SHOW for \(k+1\text{.}\)

    As in your base case, start by considering the two people (Alice and Bob) who are the smallest distance from one another. There are 2 cases to consider

    • Case 1: Suppose that someone else throws a pie at Alice or Bob. In this case, you can immediately find a person who is not hit by a pie. Why?

    • Case 2: No one else throws a pie at Alice or Bob. In this case, you need to use the induction hypothesis!