Please Login to access more options.

Exercise (The Marble Problem)

This problem is here to answer Jai's question about why we need $k\geq 1$ and not just $k>1$ (or equivalently $k\geq 4$ and not just $k>4$) in our induction hypothesis. Why must we include the base case in our induction hypothesis. This problem is an adaption of problem 10.15(a) on page 104 of Lay's book "Analysis - With an Introduction to Proof."

Consider the following conjecture.

For each $n\in\mathbb{N}$, let $P(n)$ be the statement, "Any collection of $n$ marbles consists of marbles of the same color." then $P(n)$ is true for all $n\in\mathbb{N}$.

Find the flaw in the following proof.

We know that $P(1)$ is true because any collection of 1 marble consists of marbles of the same color, namely the color of the only marble. Now assume, for some $k\in\mathbb{N}$ with $k>1$ that $P(k)$ is true. This means that any collection of $k$ marbles must consist of marbles of the same color. Consider a collection $C$ of $k+1$ marbles. Pick one of those marble (say marble $x$) and remove it. We now have a collection $C\setminus\{x\}$ that has $k$ marbles. By our induction hypothesis, we know that these marbles must all have the same color.
Note that $k>1$ means $k+1\geq 3$. So there are at least 2 marbles left in $C\setminus\{x\}$. Pick two of them and call them marbles $y$ and $z$. Note that the marbles $x$, $y$, and $z$ are 3 different marbles.
Currently, we know that $y$ and $z$ must have the same color. Now add back marble $x$ and remove marble $y$. This leaves us with the collection $C\setminus\{y\}$ which has $k$ marbles. By our induction hypothesis, all of these marbles must have the same color, which means marbles $x$ and $z$ must have the same color. We now know that $y$ and $z$ have the same color, and we know that $x$ and $z$ have the same color. This means that $x$ and $y$ must have the same color as well. In particular, this means that all the marbles in the collection $C$ must have the same color (the color of marble $z$). This completes the proof that any collection of $k+1$ marbles must have the same color. By induction, we conclude that for any $n\in\mathbb{N}$, any collection of $n$ marbles consists of marbles of the same color.

Click to see a solution. Make sure you have an answer before you reveal this.

The flaw is that we assumed for some $k>1$ that statement $P(1)$ is true. We don't know $P(k)$ is true for any $k>1$, so we have made a faulty assumption. Any conclusion we draw from this faulty assumption is vacuously true. What????? Statement $P(2)$ is false. Statement $P(2)$ does not follow from statement $P(1)$, precisely because there are not 3 different marbles in a bag with only two marbles. Pick one marble out of the bag, and you definitely have a collection with one marble of the same color. Put that marble back in and pull out the other, and statement $P(1)$ is still true. However, you don't have a third marble sitting around to compare to the ones you pulled out. Note that $P(1)$ does not imply $P(2)$, and in fact statement $P(2)$ is flat out false. The implication "if $P(2)$ then $P(3)$" is vacuously true. The implication "if $P(k)$ then $P(k+1)$" is vacuously true for every $k>1$. The implication is flat out false if $k=1$. We failed to prove that $P(k)$ implies $P(k+1)$ for every integer $k\geq 1$. We succeeded with just about all of them, but missed the one case when $k=1$.

Here's another way to explain it. Suppose you have a line of infinitely many dominoes. You have set the dominoes up so that if domino $k$ falls (for some $k>1$), then domino $k+1$ falls. Reread the previous sentence for several values of $k$.

  • if domino 2 falls, then domino 3 falls.
  • if domino 3 falls, then domino 4 falls.
  • if domino 4 falls, then domino 5 falls.
  • ...

A natural question should arise, "Does domino 2 fall if domino 1 falls?" By omitting $k=1$ from our induction assumption, we don't know if this is true or not. Now, suppose Sally comes by and knocks over the first domino. Do all the dominoes fall? We don't know. Did domino 1 knock over domino 2, or is domino 2 still standing? Who knows? The problem doesn't tell us, so we can't say anything. The induction process stops at the second domino.

When we make our induction assumption, we say "For some $k\in \mathbb{N}$ (which means $k\geq 1$)". If the base case is $n=4$, then we must say "For some $k\geq 4$ with $k\in\mathbb{N}$". Failing to include the base case in our assumption (using just $k>4$) will lead to us missing the second domino in our chain, which is the same problem as the marble dilemma above. We would know the 4th domino falls, but not if the 5th falls, and so we can't say anything about whether or not the 6th domino and beyond fell.