Strong induction

Another way to use a stronger induction hypothesis is called strong induction: To prove $P(k)$, instead of assuming that $P(k-1)$ is true, we assume that $P(1),\ldots, P(k-1)$ are all true and try to derive the validity of $P(k)$. This again goes into the principle of making the hypothesis stronger so that we can prove the statement we want.

Example 17

Every natural number $n >1$ can be written as a product of primes. (Equivalent to Lemma 1)

Proof:

We use the hypothesis:

$P(n): n$ can be written as a product of primes

Notice that if we want to prove $P(100)$, we may want to write $100 = 2 \times 50$. But then we need the fact that $50$ can be written as a prime product, so the validity of $P(99)$ is not enough for us. Let us try to prove this via a strong induction. The base case is when $n=2$, and $P(2)$ holds trivially. Now assume that $P(2), \ldots, P(n_0)$ hold. To see $P(n_0+1)$, there are two cases. If $n_0+1$ is prime, we are done. Otherwise, we can factor it into $n_0+1 = x\cdot y$ where $1 < x, y <n_0+1$. By using the validity of $P(x)$ and $P(y)$, we can write $x$ and $y$ as a product of primes, and therefore the same holds for $n_0+1$.

Exercise 6

We are interested in writing a rational number $p/q <1$ as the sum of fractions with numerators $1$. For instance, $3/5 = 1/2+1/10$ and $4/5= 1/2+1/4+1/20$. Consider the following algorithm. To write $p/q$ in this form, calculate $\frac{p}{q} - \frac{1}{\lceil q/p \rceil}$. If the result is zero, we are done; otherwise, repeat the same step on the result. Prove that this algorithm always terminates in finitely many steps.