2.8 Math Induction

Induction is one of the most powerful and commonly-used proof techniques in mathematics, especially discrete mathematics. Many problems that involve integers can be solved using induction. The general steps for proof by induction are the following:

• State that the proof uses induction and define an appropriate predicate $P(n)$.
• Prove the base case $P(1)$, or any other smallest number $n$ for the predicate to be true.
• Prove that $P(n)$ implies $P(n+1)$ for every integer $n$. Alternatively, in a strong induction argument, you prove that $P(1),\ P(2),\ \cdots,$ and $P(n)$ together imply $P(n+1)$.

In most cases, the real difficulty lies not in the induction step, but to formulate the problem as an induction problem and come up with the appropriate predicate $P(n)$. The simplified version of the problem can often help you identify $P(n)$.

Coin split problem

You split 1000 coins into two piles and count the number of coins in each pile. If there are $x$ coins in pile one and $y$ coins in pile two, you multiple $x$ by $y$ to get $xy$. Then you split both piles further, repeat the same counting and multiplication process, and add the new multiplication results to the original. For example, you split $x$ to $x_1$ and $x_2$, $y$ to $y_1$ and $y_2$, then the sum is $xy+x_1x_2+y_1y_2$. The same process is repeated until you only have piles of 1 stone each. What is the final sum? (The final 1’s are not included in the sum.) Prove that you always get the same answer no matter how the piles are divided.

Solution: Let $n$ be the number of the coins and $f(n)$ be the final sum. It is unlikely that a solution will jump to our mind since the number $n=1000$ is a large number. If you aren’t sure how to approach the problem, it never hurts to begin with the simplest cases and try to find a pattern. For this problem, the base case has $n=2$. Clearly the only split is $1+1$ and the final sum is 1. When $n=3$, the first split is $2+1$ and we have $xy=2$ and the 2-coin pile will further give an extra multiplication result 1, so the final sum is 3. This analysis also gives the hint that when $n$ coins are split into $x$ and $n-x$ coins, the total sum will be $f(n)=x(n-x)+f(x)+f(n-x)$. 4 coins can be split into $2+2$ or $3+1$. For either case we can apply $x(n-x)+f(x)+f(n-x)$ and yields the same final sum 6.

Claim: For $n$ coins, independent of intermediate splits, the final sum is $\displaystyle\frac{n(n-1)}2$. ¹⁷

So how do we prove it? The answer should be clear to you: by strong induction. We have proved the claim for the base cases $n=2,3,4$. Assume the claim is true for $n=2,\cdots,N-1$ coins, we need to prove that it holds for $n=N$ coins as well. Again we apply the equation $f(n)=x(n-x)+f(x)+f(n-x)$. If $N$ coins are split into $x$ coins and $N-x$ coins, we have

So indeed it holds for $n=N$ as well and $f(n)=\displaystyle\frac{n(n-1)}2$ is true for any $n\ge2$. Applying the conclusion to $n=1000$, we have $f(n)=1000\times999/2$.

Chocolate bar problem

A chocolate bar has 6 rows and 8 columns (48 small $1\times1$ squares). You break it into individual squares by making a number of breaks. Each time, break one rectangle into two smaller rectangles. For example, in the first step you can break the $6\times8$ chocolate bar into a $6\times3$ one and a $6\times5$ one. What is the total number of breaks needed in order to break the chocolate bar into 48 small squares?

Solution: Let $m$ be the number of the rows of the chocolate bar and $n$ be the number of columns. Since there is nothing special for the case $m=6$ and $n=8$, we should find a general solution for all $m$ and $n$. Let’s begin with the base case where $m=1$ and $n=1$. The number of breaks needed is clearly 0. For $m>1$ and $n=1$, the number of breaks is $m-1$; similarly for $m=1$ and $n>1$, the number of breaks is $n-1$. So for any $m$ and $n$, if we break the chocolate into $m$ rows first, which takes $m-1$ breaks, and then break each row into $n$ small pieces, which takes $m(n-1)$ breaks, the total number of breaks is $(m-1)+m(n-1)=mn-1$. If we breaks it into $n$ columns first and then break each column into $m$ small pieces, the total number of breaks is also $mn-1$. But is the total number of breaks always $mn-1$ for other sequences of breaks? Of course it is. We can prove it using strong induction.

We have shown the number of breaks is $mn-1$ for base cases $m\ge1,n=1$ and $m=1,n\ge1$. To prove it for a general $m\times n$ case, let’s assume the statement is true for cases where $rows<m,\ columns\le n$ and $rows\le m,\ columns<n$. If the first break is along a row and it is broken into two smaller pieces $m\times n_1$ and $m\times(n-n_1)$, then the total number of breaks is $1+(m\times n_1-1)+(m\times(n-n_1)-1)=mn-1$. Here we use the results for $rows\le m,\ columns<n$. Similarly, if it is broken into two pieces $m_1\times n$ and $(m-m_1)\times n$, the total number of breaks is $1+(m_1\times n-1)+((m-m_1)\times n-1)=mn-1$. So the total number of breaks is always $mn-1$ in order to break the chocolate bar into $m\times n$ small pieces. For the case $m=6$ and $n=8$, the number of breaks is 47.

Although induction is the standard approach used to solve this problem, there is actually a simpler solution if you’ve noticed an important fact: the number of pieces always increases by 1 with each break since it always breaks one piece into two. In the beginning, we have a single piece. In the end, we will have $mn$ pieces. So the number of breaks must be $mn-1$.

Race track

Suppose that you are on a one-way circular race track. There are $N$ gas cans randomly placed on different locations of the track and the total sum of the gas in these cans is enough for your car to run exactly one circle. Assume that your car has no gas in the gas tank initially, but you can put your car at any location on the track and you can pick up the gas cans along the way to fill in your gas tank. Can you always choose a starting position on the track so that your car can complete the entire circle? ¹⁸

Solution: If you get stuck as to how to solve the problem, again start with the simplest cases ($N=1,2$) and consider using an induction approach. Without loss of generality, let’s assume that the circle has circumference of 1. For $N=1$, the problem is trivial. Just start at where the gas can is. For $N=2$, The problem is still simple. Let’s use a figure to visualize the approach. As shown in Figure 2.4A, the amount of gas in can 1 and can 2, expressed as the distance the car can travel, are $x_1$ and $x_2$ respectively, so $x_1+x_2=1$. The corresponding segments are $y_1$ and $y_2$, so $y_1+y_2=1$. Since $x_1+x_2=1$ and $y_1+y_2=1$, we must have $x_1\ge y_1$ or $x_2\ge y_2$ ($x_1<y_1$ and $x_2<y_2$ cannot both be true). If $x_1\ge y_1$, we can start at gas can 1, which has enough gas to reach gas can 2, and get more gas from gas can 2 to finish the whole circle. Otherwise, we will just start at gas can 2 and pick up gas can 1 along the way to finish the whole circle.

The argument for $N=2$ also gives us the hint for the induction step. Now we want to show that if the statement holds for $N=n$, then the same statement also holds for $N=n+1$. As shown in Figure 2.4B, we have $x_1+x_2+\cdots+x_{n+1}=1$ and $y_1+y_2+\cdots+y_{n+1}=1$ for $N=n+1$. So there must exist at least one $i,1\le i\le n+1$, that has $x_i\ge y_i$. That means whenever the car reaches $x_i$, it can reach $x_{i+1}$ with more gas (For $i=n+1$, it goes to $i=1$ instead). In other words, we can actually “combine” $x_i$ and $x_{i+1}$ to one gas can at the position of $x_i$ with an amount of gas $x_i+x_{i+1}$ (and eliminate the gas can $i+1$). But such combination reduces the $N=n+1$ problem to $N=n$, for 31 which the statement holds. So the statement also holds for $N=n+1$. Hence we can always choose a starting position on the track to complete the entire circle for any $N$.

There is also an alternative approach to this problem that provides a solution to the starting point. Let’s imagine that you have another car with enough gas to finish the circle. You put that car at the position of a randomly chosen gas can and drive the car for a full circle. Whenever you reach a gas can (including at the initial position), you measure the amount of gas in your gas tank before you add the gas from the can to your gas tank. After you finish the circle, read through your measurement records and find the lowest measurement. The gas can position corresponding to the lowest measurement should be your starting position if the car has no gas initially. (It may take some thinking to fully understand this argument. I’d recommend that you again draw a figure and give this argument some careful thoughts if you don’t find the reasoning obvious.)