Strong Induction

Section 4.6 Strong Induction

Subsection Going farther back

Investigate!

Start with a square piece of paper. You want to cut this square into smaller squares, leaving no waste (every piece of paper you end up with must be a square). Obviously it is possible to cut the square into 4 squares. You can also cut it into 9 squares. It turns out you can cut the square into 7 squares (although not all the same size). What other numbers of squares could you end up with?

Sometimes, to prove that $P(k+1)$ is true, it would be helpful to know that $P(k)$ and $P(k-1)$ and $P(k-2)$ are all true. Consider the following puzzle:

You have a rectangular chocolate bar, made up of $n$ identical squares of chocolate. You can take such a bar and break it along any row or column. How many times will you have to break the bar to reduce it to $n$ single chocolate squares?

At first, this question might seem impossible. Perhaps I meant to ask for the smallest number of breaks needed? Let’s investigate.

Start with some small cases. If $n=2\text{,}$ you must have a $1\times 2$ rectangle, which can be reduced to single pieces in one break. With $n=3\text{,}$ we must have a $1\times 3$ bar, which requires two breaks: the first break creates a single square and a $1\times 2$ bar, which we know takes one (more) break.

What about $n=4\text{?}$ Now we could have a $2\times 2$ bar, or a $1 \times 4$ bar. In the first case, break the bar into two $2\times 2$ bars, each which require one more break (that’s a total of three breaks required). If we started with a $1 \times 4$ bar, we have choices for our first break. We could break the bar in half, creating two $1\times 2$ bars, or we could break off a single square, leaving a $1\times 3$ bar. But either way, we still need two more breaks, giving a total of three.

It is starting to look like no matter how we break the bar (and no matter how the $n$ squares are arranged into a rectangle), we will always have the same number of breaks required. It also looks like that number is one less than $n\text{:}$

Conjecture 4.6.1.

Given a $n$-square rectangular chocolate bar, it always takes $n-1$ breaks to reduce the bar to single squares.

It makes sense to prove this by induction because after breaking the bar once, you are left with smaller chocolate bars. Reducing to smaller cases is what induction is all about. We can inductively assume we already know how to deal with these smaller bars. The problem is, if we are trying to prove the inductive case about a $(k+1)$-square bar, we don’t know that after the first break the remaining bar will have $k$ squares. So we really need to assume that our conjecture is true for all cases less than $k+1\text{.}$

Is it valid to make this stronger assumption? Remember, in induction we are attempting to prove that $P(n)$ is true for all $n\text{.}$ What if that were not the case? Then there would be some first $n_0$ for which $P(n_0)$ was false. Since $n_0$ is the first counterexample, we know that $P(n)$ is true for all $n \lt n_0\text{.}$ Now we proceed to prove that $P(n_0)$ is actually true, based on the assumption that $P(n)$ is true for all smaller $n\text{.}$

This is quite an advantage: we now have a stronger inductive hypothesis. We can assume that $P(1)\text{,}$ $P(2)\text{,}$ $P(3)\text{,}$ … $P(k)$ is true, just to show that $P(k+1)$ is true. Previously, we just assumed $P(k)$ for this purpose.

It is slightly easier if we change our variables for strong induction. Here is what the formal proof would look like:

Strong Induction Proof Structure.

Again, start by saying what you want to prove: “Let $P(n)$ be the statement…” Then establish two facts:

Base case: Prove that $P(0)$ is true.
Inductive case: Assume $P(k)$ is true for all $k \lt n\text{.}$ Prove that $P(n)$ is true.

Conclude, “therefore, by strong induction, $P(n)$ is true for all $n \gt 0\text{.}$”

Of course, it is acceptable to replace 0 with a larger base case if needed.

Technically, strong induction does not require you to prove a separate base case. This is because when proving the inductive case, you must show that $P(0)$ is true, assuming $P(k)$ is true for all $k \lt 0\text{.}$ But this is not any help so you end up proving $P(0)$ anyway. To be on the safe side, we will always include the base case separately.

Let’s prove our conjecture about the chocolate bar puzzle:

Proof.

Let $P(n)$ be the statement, “it takes $n-1$ breaks to reduce a $n$-square chocolate bar to single squares.”

Base case: Consider $P(2)\text{.}$ The squares must be arranged into a $1\times 2$ rectangle, and we require $2-1 = 1$ breaks to reduce this to single squares.

Inductive case: Fix an arbitrary $n\ge 2$ and assume $P(k)$ is true for all $k \lt n\text{.}$ Consider a $n$-square rectangular chocolate bar. Break the bar once along any row or column. This results in two chocolate bars, say of sizes $a$ and $b\text{.}$ That is, we have an $a$-square rectangular chocolate bar, a $b$-square rectangular chocolate bar, and $a+b = n\text{.}$

We also know that $a \lt n$ and $b \lt n\text{,}$ so by our inductive hypothesis, $P(a)$ and $P(b)$ are true. To reduce the $a$-square bar to single squares takes $a-1$ breaks; to reduce the $b$-square bar to single squares takes $b-1$ breaks. Doing this results in our original bar being reduced to single squares. All together it took the initial break, plus the $a-1$ and $b-1$ breaks, for a total of $1+a-1+b-1 = a+b-1 = n-1$ breaks. Thus $P(n)$ is true.

Therefore, by strong induction, $P(n)$ is true for all $n \ge 2\text{.}$

Here is a more mathematically relevant example:

Example 4.6.2.

Prove that any natural number greater than 1 is either prime or can be written as the product of primes.

Solution.

First, the idea: if we take some number $n\text{,}$ maybe it is prime. If so, we are done. If not, then it is composite, so it is the product of two smaller numbers. Each of these factors is smaller than $n$ (but at least 2), so we can repeat the argument with these numbers. We have reduced to a smaller case.

Now the formal proof:

Proof.

Let $P(n)$ be the statement, “$n$ is either prime or can be written as the product of primes.” We will prove $P(n)$ is true for all $n \ge 2\text{.}$

Base case: $P(2)$ is true because $2$ is indeed prime.

Inductive case: assume $P(k)$ is true for all $k \lt n\text{.}$ We want to show that $P(n)$ is true. That is, we want to show that $n$ is either prime or is the product of primes. If $n$ is prime, we are done. If not, then $n$ has more than 2 divisors, so we can write $n = m_1 \cdot m_2\text{,}$ with $m_1$ and $m_2$ less than $n$ (and greater than 1). By the inductive hypothesis, $m_1$ and $m_2$ are each either prime or can be written as the product of primes. In either case, we have that $n$ is written as the product of primes.

Thus by the strong induction, $P(n)$ is true for all $n \ge 2\text{.}$

Whether you use regular induction or strong induction depends on the statement you want to prove. If you wanted to be safe, you could always use strong induction. It really is stronger, so can accomplish everything “weak” induction can. That said, using regular induction is often easier since there is only one place you can use the induction hypothesis. There is also something to be said for elegance in proofs. If you can prove a statement using simpler tools, it is nice to do so.

As a final contrast between the two forms of induction, consider once more the stamp problem. Regular induction worked by showing how to increase postage by one cent (either replacing three 5-cent stamps with two 8-cent stamps, or three 8-cent stamps with five 5-cent stamps). We could give a slightly different proof using strong induction. First, we could show five base cases: it is possible to make 28, 29, 30, 31, and 32 cents (we would actually say how each of these is made). Now assume that it is possible to make $k$ cents of postage for all $k \lt n$ as long as $k \ge 28\text{.}$ As long as $n > 32\text{,}$ this means in particular we can make $k = n-5$ cents. Now add a 5-cent stamp to get make $n$ cents.

Reading Questions Reading Questions

Exercises Practice Problems

Practice problems coming soon.

Exercises Additional Exercises

1.

Suppose a football team only scores 3-point field goals and 7-point touchdowns (ignore the possibilities of safeties, missed extra points, and two point conversions). Prove, using strong induction, that the team can get any number of points 12 or greater.

Hint.

If you have three base cases, can you always be sure you can get three points more?

2.

Prove using strong induction that the sum of the interior angles of a convex $n$-gon is $(n-2)\cdot 180^\circ\text{.}$ (A convex $n$-gon is a polygon with $n$ sides for which each interior angle is less than $180^\circ\text{.}$)

Hint.

Start with $(k+1)$-gon and divide it into two smaller polygons.

3.

Prove that every positive integer is either a power of 2, or can be written as the sum of distinct powers of 2.

Solution.

The proof will be by strong induction.

Proof.

Let $P(n)$ be the statement “$n$ is either a power of 2 or can be written as the sum of distinct powers of 2.” We will show that $P(n)$ is true for all $n \ge 1\text{.}$

Base case: $1 = 2^0$ is a power of 2, so $P(1)$ is true.

Inductive case: Suppose $P(k)$ is true for all $k \lt n\text{.}$ Now if $n$ is a power of 2, we are done. If not, let $2^x$ be the largest power of 2 strictly less than $n\text{.}$ Consider $n - 2^x\text{,}$ which is a smaller number, in fact smaller than both $n$ and $2^x\text{.}$ Thus $n-2^x$ is either a power of 2 or can be written as the sum of distinct powers of 2, but none of them are going to be $2^x\text{,}$ so the together with $2^x$ we have written $n$ as the sum of distinct powers of 2.

Therefore, by the principle of (strong) mathematical induction, $P(n)$ is true for all $n \ge 1\text{.}$

4.

Prove, using strong induction, that every natural number is either a Fibonacci number or can be written as the sum of distinct Fibonacci numbers.

Hint.

As with the previous question, we will want to subtract something from $n$ in the inductive step. There we subtracted the largest power of 2 less than $n\text{.}$ So what should you subtract here?

Note, you will still need to take care here that the sum you get from the inductive hypothesis, together with the number you subtracted will be a sum of distinct Fibonacci numbers. In fact, you could prove that the Fibonacci numbers in the sum are non-consecutive!

5.

Suppose that a particular real number $x$ has the property that $x + \frac{1}{x}$ is an integer. Prove that $x^n + \frac{1}{x^n}$ is an integer for all natural numbers $n\text{.}$

Hint.

You will need to use strong induction. For the inductive case, try multiplying $\left (x^k + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right)$ and collect which terms together are integers.

6.

Here is an example of a more complicated induction technique called double induction.

You will prove that the Fibonacci numbers satisfy the identity $F_n^2 + F_{n+1}^2 = F_{2n+1}\text{.}$ One way to do this is to prove the more general identity,

\begin{equation*} F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\text{,} \end{equation*}

and realize that when $m = n$ we get our desired result.

Note that we now have two variables, so we want to prove this for all $m \ge 0$ and all $n \ge 0$ at the same time. For each such pair $(m,n)\text{,}$ let $P(m,n)$ be the statement $F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}$

(a)

First fix $m = 0$ and give a proof by mathematical induction that $P(0,n)$ holds for all $n \ge 0\text{.}$ Note this proof will be very easy.

(b)

Now fix an arbitrary $n$ and give a proof by strong mathematical induction that $P(m,n)$ holds for all $m \ge 0\text{.}$

(c)

You can now conclude that $P(m,n)$ holds for all $m,n\ge 0\text{.}$ Do you believe that? Explain why this sort of induction is valid. For example, why do your proofs above guarantee that $P(2,3)$ is true?

7.

Given a square, you can cut the square into smaller squares by cutting along lines parallel to the sides of the original square (these lines do not need to travel the entire side length of the original square). For example, by cutting along the lines below, you will divide a square into 6 smaller squares:

$One large square with five squares of half the side length wrapping around the top and right side, forming an even larger square.$

Prove, using strong induction, that it is possible to cut a square into $n$ smaller squares for any $n \ge 6\text{.}$

Hint.

You will need three base cases. This is a very good hint actually, as it suggests that to prove $P(n)$ is true, you would want to use the fact that $P(n-3)$ is true. So somehow you need to increase the number of squares by 3.

Prev Top Next