Strong Induction Proofs

The Principle of Strong Induction

In a standard inductive proof, the inductive step involves proving that $P(k)⟹P(k+1)$. However, some problems are structured such that the truth of $P(k+1)$ depends not on $P(k)$ alone, but on one or more earlier cases, like $P(k-1)$ or $P(k/2)$. For these situations, we need a stronger inductive hypothesis.

Strong induction provides exactly this. The structure is as follows:

1. Base Case(s): Prove that one or more initial statements, such as $P(1)$, $P(2)$, etc., are true.
2. Inductive Step: Prove that for any $k$ greater than or equal to the base cases, if $P(j)$ is true for all $j$ from the beginning up to $k$, then $P(k+1)$ is also true.

The following resource provides a formal and concise definition of this principle.

A natural question arises: if we are allowed to assume more, does this make strong induction a logically "stronger" proof method? The answer, perhaps surprisingly, is no. Strong induction and weak (standard) induction are logically equivalent. Any proof done with one can be rewritten using the other. For a rigorous understanding, it's valuable to see how strong induction can be proven as valid using the principle of weak induction we've already accepted.

The following video lecture provides a clear and elegant proof of this equivalence.

When is Strong Induction Necessary?

The true value of strong induction becomes apparent when proving properties of objects or sequences defined by recurrence relations that refer to more than just the previous term.

Example 1: Recurrence Relations

Consider a sequence $(f_n)$ defined recursively. If the formula for $f_{k+1}$ depends on both $f_k$ and $f_{k-1}$, then assuming only the property for $f_k$ is insufficient. We need to know the property holds for $f_{k-1}$ as well, which is exactly what the strong induction hypothesis provides.

This type of problem also highlights a key practical difference: strong induction proofs often require multiple base cases. If your inductive step needs to "look back" two steps (from $k+1$ to $k-1$), you need to manually verify the first two cases to ensure the chain of logic can start.

The following video provides an excellent walkthrough of this scenario.

Let's formalize the structure of that proof.

Proposition: Let a sequence be defined by $f(1)=3$, $f(2)=5$, and $f(n)=2f(n-1)-f(n-2)$ for $n\ge 3$. Prove that $f(n)=2n+1$ for all $n\in \mathbb{N}$.

Proof. We proceed by strong induction on $n$. Let $P(n)$ be the statement $f(n)=2n+1$.

1. Base Cases: Since the recurrence for $f(n)$ depends on the two preceding terms, we must verify the first two cases.

• For $n=1$: $f(1)=3$. The formula gives $2(1)+1=3$. So $P(1)$ is true.
• For $n=2$: $f(2)=5$. The formula gives $2(2)+1=5$. So $P(2)$ is true.

2. Inductive Step: Let $k\ge 2$ be an arbitrary integer.
Inductive Hypothesis: Assume $P(j)$ is true for all integers $j$ such that $1\le j\le k$. That is, assume $f(j)=2j+1$ for $1\le j\le k$.
Goal: We want to prove that $P(k+1)$ is true, i.e., $f(k+1)=2(k+1)+1=2k+3$.

Since $k\ge 2$, we have $k+1\ge 3$. Therefore, we can use the recurrence relation:
$f(k+1)=2f(k)-f(k-1)$
Since $k$ and $k-1$ are both within the range $[1,k]$, we can apply the inductive hypothesis to both $f(k)$ and $f(k-1)$:

This is the desired result for $P(k+1)$.

By the principle of strong induction, $f(n)=2n+1$ is true for all $n\in \mathbb{N}$. □

Example 2: Prime Factorization

A beautiful and fundamental application of strong induction is in proving the existence part of the Fundamental Theorem of Arithmetic. When we factor an integer $n$, we break it into smaller integers $a$ and $b$ where $n=ab$. We don't know what $a$ and $b$ are, only that they are smaller than $n$. Standard induction would be useless here, but strong induction is perfect.

Example 3: The Postage Stamp Problem

Problems involving combinations, like making a certain amount of postage from stamps of given denominations, are also classic candidates for strong induction. To make postage for $k+1$ cents, a clever strategy might be to first make postage for a smaller amount (say, $k-2$) and then add a 3-cent stamp. This "step back" of 3 dictates that we will need to verify 3 consecutive base cases.

Conclusion

Today we have added strong induction to our toolkit of proof techniques. While logically equivalent to the standard induction we learned previously, its utility in specific contexts makes it indispensable.

Here are the key takeaways from this lesson:

• Strong Inductive Hypothesis: Instead of assuming $P(k)$ is true, we assume $P(j)$ is true for all cases $j$ from the base case up to $k$.
• When to Use It: Strong induction is particularly effective for proofs involving recurrence relations that look back more than one step, or for problems where a case $n$ is reduced to a smaller, but not necessarily $n-1$, case (like factorization).
• Multiple Base Cases: The number of steps "looked back" in the inductive step determines the number of base cases you must verify manually to anchor the proof.

You have now completed the first module on the foundations of logic and proofs. You are equipped with direct proofs, contrapositive, contradiction, and both standard and strong induction. These logical frameworks are the bedrock upon which all of modern analysis is built.

In our next lesson, we will begin Module 2: Sets and Functions. We will leave the world of pure logic and begin applying these proof techniques to the fundamental objects of mathematics, starting with the language of sets.