Strong Induction

Strong induction is a variant of induction, in which we assume that the statement holds for all values preceding \(k\). This provides us with more information to use, when trying to prove the statement.

Now that we know how standard induction works, it's time to look at a variant of it, strong induction. In many ways, strong induction is similar to normal induction. There is however a difference in the inductive hypothesis. Normally, when using induction, we assume that \(P(k)\) is true to prove \(P(k+1)\). In strong induction, we assume that all of \(P(1), P(2), . . . , P(k)\) are true to prove \(P(k + 1)\).

Why would we need to do that? Let's go back to our domino analogy. Say that you have infinitely many dominoes arranged in a line. But this time, the weight of the \(k^\text{th}\) domino isn't enough to knock down the \((k+1)^\text{th}\) domino. Knocking down the \((k+1)^\text{th}\) domino requires the weight of all the dominoes before it. Even now, if you are able to knock down the first domino, you can prove that all the dominoes will eventually fall.

The reason why this is called "strong induction" is that we use more statements in the inductive hypothesis. Let's write what we've learnt till now a bit more formally.

Proof by strong induction

Step 1. Demonstrate the base case:
This is where you verify that \(P(k_0)\) is true. In most cases, \(k_0=1.\)

Step 2. Prove the inductive step:
This is where you assume that all of \(P(k_0)\), \(P(k_0+1), P(k_0+2), \ldots, P(k)\) are true (our inductive hypothesis). Then you show that \(P(k+1)\) is true.

The proof of why this works is similar to that of standard induction.

[Fundamental Theorem of Arithmetic]
Every integer \(n\geq 2\) can be written uniquely as the product of prime numbers.

---

Base case: This is clearly true for \(n=2\).

Inductive step: Suppose the statement is true for \(n=2, 3, 4, \ldots, k.\)

If \((k+1)\) is prime, then we are done. Otherwise, \((k+1)\) has a smallest prime factor, which we denote by \(p.\) Let \(k+1=p\times N.\) Since \(N< k\), by our inductive hypothesis, \(N\) can be written uniquely as the product of prime numbers. That means \(k+1=p\times N\) can also be written uniquely as a product of primes. We're done! \(_\square\)

Notice how the assumption that \(P(k)\) is true wasn't enough to prove that \(P(k+1)\) is true. We actually needed another statement instead.

The Fibonacci sequence is defined by \( F_{n+2} = F_{n+1} + F_n \) for integers \( n \geq 0 \), with starting values \( F_1 = F_ 2 = 1 \). Show that

\[ F_n = \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 + \sqrt{5} } { 2} \right)^n - \left ( \frac{1 - \sqrt{5} } { 2} \right)^n \right]. \]

---

Base case:
For \( n = 1 \), we have \( LHS: F_1 =1 \) and \( RHS: \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 + \sqrt{5} } { 2} \right)^1 - \left ( \frac{1 - \sqrt{5} } { 2} \right)^1 \right] = \frac{ 1 } { \sqrt{5} } \left[ \frac{ 2 \sqrt{5} } { 2} \right] = 1 \).

For \( n = 2 \), we have \( LHS: F_2 = 1 \) and \( RHS: \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 + \sqrt{5} } { 2} \right)^2 - \left ( \frac{1 - \sqrt{5} } { 2} \right)^2 \right] = \frac{ 1 } { \sqrt{5} } \left[ \frac{ 4 \sqrt{5} } { 4} \right] = 1 \).

Induction step: Suppose that the statement is true for \( n = k-1 \) and \( k \).
Then, we have

\[\begin{align} F_{n+1} & = F_n + F_{n-1} \\\\ & = \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 + \sqrt{5} } { 2} \right)^n - \left ( \frac{1 - \sqrt{5} } { 2} \right)^n \right] + \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 + \sqrt{5} } { 2} \right)^{n-1} - \left ( \frac{1 - \sqrt{5} } { 2} \right)^{n-1} \right] \\\\ & = \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 + \sqrt{5} } { 2} \right)^n + \left ( \frac{1 + \sqrt{5} } { 2} \right)^{n-1} \right] - \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 - \sqrt{5} } { 2} \right)^n + \left ( \frac{1 - \sqrt{5} } { 2} \right)^{n-1} \right] \\\\ & = \frac{ 1}{ \sqrt{5} } \left [ \left ( \frac{1 + \sqrt{5} } { 2} \right)^{n+1} - \left ( \frac{1 - \sqrt{5} } { 2} \right)^{n+1} \right]. \end{align} \]

Hence, the proposition is true. \(_\square\)

Note that in this case, we did not need to use all of prior statements, but just the previous 2.

A chocolate bar consists of unit squares arranged in an \( n \times m \) rectangular grid. You may split the bar into individual unit squares, by breaking along the lines. What is the number of breaks required?

---

We will show that the number of breaks needed is \( nm - 1 \).

Base Case:
For a \( 1 \times 1 \) square, we are already done, so no steps are needed.
\( 1 \times 1 - 1 = 0 \), so the base case is true.

Induction Step: Let \( P(n,m) \) denote the number of breaks needed to split up an \( n \times m \) square.

WLOG, we may assume that the first break is along a row, and we get an \( n_1 \times m \) and an \( n_2 \times m \) bar, where \( n_1 + n_2 = n \).
By the induction hypothesis, the number of further breaks that we need is \( n_1 \times m - 1 \) and \( n_2 \times m - 1 \).
Hence, the total number of breaks that we need is

\[ 1 + ( n_1 \times m -1 ) + ( n_2 \times m - 1 ) = (n_1 + n_2) \times m - 1 = n \times m - 1.\ _\square \]

Note: This problem can also be approached using Invariance principle.

A country has \(n\) cities. Any two cities are connected by a one-way road. Show that there is a route that passes through every city.

---

If you have already read the wiki on standard induction, this problem may seem familiar. Yes, we did prove this in that article (if you haven't read that wiki, now would be a good time to do that). We'll see how stronger induction produces a shorter and cleaner solution.

As we've already seen, our base case for this is true.

Now we make the "strong hypothesis." We assume that our statement is true for any set of \(k\) or fewer cities.

Now, for a set of \((k+1)\) cities, take out the \((k+1)^\text{th}\) city \(C_{k+1}\) and split the rest of them into two sets \(A\) and \(B\). \(A\) will contain all the cities that lead to \(C_{k+1}\) and \(B\) will contain all the cities \(C_{k+1}\) leads to.

Since \(A\) has \(k\) or fewer cities in it, by the inductive hypothesis, there is a route that passes through every city in \(A\). The same argument holds for \(B\).

Now start with the route that passes through every city in \(A\). Then go to \(C_{k+1}\). You can do that because all the cities in \(A\) lead to \(C_{k+1}\). After that, go to the route that passes through every city in \(B\). Again, you can do that because \(C_{k+1}\) leads to every city in \(B\).

And just like that, our proof is complete! \(_\square\)

This proof is almost identical to the proof of standard induction. Can you spot the differences?

Let \(S\) be a set of positive integers with the following properties:

1. The integer 1 belongs to the set.
2. Whenever the integers \(1, 2, 3, \ldots, k\) are in \(S\), the next integer \(k+1\) must also be in \(S\).

Then \(S\) is the set of all positive integers.

We will prove this theorem by contradiction.

Let \(T\) be the set of all positive integers not in \(S\). By assumption, \(T\) is non-empty. Hence it must contain a smallest element, which we will denote by \(\alpha\).

By (1), \(0 < \alpha-1 < \alpha\). Since \( \alpha\) is the smallest integer in \(T\), this implies that \( 1, 2, \ldots, \alpha - 1 \not \in T \implies 1, 2, \ldots, \alpha -1 \in S \).
By (2), \(S\) must also contain \( (\alpha-1)+1=\alpha\). This contradicts the assumption that \(\alpha\subset\) \(T\).

Hence set \(T\) is empty, and set \(S\) contains all positive integers. \(_\square \)

1. Show that every integer \(N\) can be written in the form \(N=2^k l\), where \(k\) is a non-negative integer and \(l\) is an odd integer.

2. [APMO '99] Let \(\{a_i\}\) be a sequence of real numbers that satisfy \( a_{i+j} \leq a_i + a_j\) \(\forall i, j\). Prove that \[\frac{ a_1}{1} + \frac {a_2}{2} + \cdots+ \frac {a_n}{n} \geq a_n. \]

3. Prove that every positive integer \(n\) has a binary expression. Namely, that there exists integers \( c_i \in \{ 0, 1 \} \) such that \[ n = c_r 2^r + c_{r-1} 2^{r-1} + \cdots + c_2 2^2 + c_1 2^1 + c_0 2^ 0. \]

4. Consider the sequence defined as \( d_1 = 1, d_2 = 2, d_3 = 3, \) and \( d_{n+3} = d_{n+2} + d_{n+1} + d_n \) for all positive integers \(n\).
   Show that \( d_n < 2 ^ n \).