Proving Recurrence Relations with Strong Induction

From Induction to Strong Induction

Let's revisit the ladder analogy from our previous lesson. Standard induction says that if you can get on the first rung (the base case) and you know how to climb from any rung $k$ to the next one, $k+1$ (the inductive step), then you can climb the whole ladder.

Strong induction makes a seemingly small but profoundly powerful change to the inductive step. It says: if you can get on the first rung, and you know how to get to rung $k+1$ assuming you have already climbed all the rungs up to and including rung $k$, then you can climb the whole ladder.

Instead of just assuming $P(k)$ is true, we get to assume that $P(1),P(2),\dots ,P(k)$ are all true. This stronger assumption gives us more ammunition to prove the case for $P(k+1)$.

For a formal definition and a great visual metaphor, let's turn to the "Discrete Mathematics: An Open Introduction" textbook.

The key difference lies in the inductive hypothesis.

• Weak Induction Hypothesis: Assume $P(k)$ is true for a particular integer $k$.
• Strong Induction Hypothesis: Assume $P(j)$ is true for all integers $j$ from the base case up to $k$.

While it seems "stronger," anything provable with strong induction can also be proven with weak induction (and vice-versa). We use strong induction because it often provides a more natural and direct way to structure a proof, especially for problems involving recurrence relations or "divide and conquer" logic.

Recurrence Relations: The Natural Home for Strong Induction

A recurrence relation defines a term in a sequence based on its preceding terms. For example, the famous Fibonacci sequence is defined by $F_n=F_{n-1}+F_{n-2}$. If you want to prove a property about $F_{k+1}$, you'll almost certainly need information about both $F_k$ and $F_{k-1}$. An assumption about just $F_k$ (from weak induction) won't be enough. You need the strong induction hypothesis.

This leads to a crucial question: how many base cases do you need to prove?

The Rule of Thumb: If your recurrence relation goes back m steps (like the Fibonacci sequence goes back 2 steps), you will need to prove m initial base cases to "prime the pump" for the induction.

The following video explains this critical connection between the depth of the recurrence and the number of required base cases. It uses a clear example to demonstrate why this is necessary.

Worked Example: Proving a Closed Form for a Recurrence

Let's now apply this to a full-fledged problem. Consider a sequence defined by:

• $s_0=0$
• $s_1=4$
• $s_n=6s_{n-1}-5s_{n-2}$ for $n\ge 2$

Suppose we conjecture that the closed-form formula for this sequence is $s_n=5^n-1$. Let's prove it using strong induction. The video below provides a masterful walkthrough of this exact proof.

This example is the quintessential application of strong induction for a recurrence relation, directly addressing our learning goal. The structure is clean: establish enough base cases, assume the property holds for all prior values, and use that powerful assumption to prove the next step.

Beyond Recurrences: The Chocolate Bar Problem

Strong induction isn't just for recurrence relations. It's essential for any problem where a larger structure is broken down into smaller, not necessarily predictable, pieces. A classic competitive math problem that illustrates this is the "chocolate bar problem."

Problem: You have a rectangular chocolate bar made of $n$ squares. A "break" consists of taking one piece of chocolate and breaking it along a single horizontal or vertical line. How many breaks are required to separate the bar into $n$ individual squares?

It turns out the answer is always $n-1$, regardless of the bar's shape or how you choose to break it. Let's prove this. When you make the first break, you split the $n$-square bar into two smaller pieces of size $a$ and $b$, where $a+b=n$. To know the total breaks, you need to know how many breaks it takes for pieces of size $a$ and $b$. Since $a$ and $b$ could be anything, you need the strong inductive hypothesis to assume the result holds for all smaller pieces.

The following reading provides a concise and elegant proof.

A Deeper Application: The Fundamental Theorem of Arithmetic

To see the true power of this method, consider the proof of one of the cornerstones of mathematics: the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 is either prime or can be written as a product of primes.

How would you prove this with induction? Let's try to prove $P(k+1)$. If $k+1$ is prime, we're done. If it's not, it's composite, so $k+1=a\cdot b$ for some smaller integers $a$ and $b$. To continue, we need to know that $P(a)$ and $P(b)$ are true. But we don't know what $a$ and $b$ are! They aren't necessarily $k$ or $k-1$. They could be any integers smaller than $k+1$. This is where strong induction becomes essential.

The proof is remarkably simple once you have the right tool.

Key Takeaways

• Strong vs. Weak Induction: The difference is the inductive hypothesis. Weak induction assumes $P(k)$, while strong induction assumes $P(j)$ for all base $\le j\le k$.
• When to Use Strong Induction: It is essential for problems where the case for $k+1$ depends on multiple preceding cases or on subproblems of arbitrary smaller sizes. This includes most non-trivial recurrence relations and "divide and conquer" problems.
• Determine Your Base Cases: The structure of the inductive step dictates the number of base cases you need. If your proof for $P(k+1)$ needs to reach back to $P(k-m)$, you will likely need to prove $m+1$ base cases to get the induction started safely.

Looking Ahead

We have now thoroughly covered the major variants of mathematical induction. You've seen how to apply standard induction to prove summation identities and how to use strong induction for more complex structures like recurrence relations. In our next lesson, we will shift gears and introduce an entirely different, and often more elegant, proof technique in combinatorics: the combinatorial proof, where we prove identities by showing that both sides of an equation count the same set of objects, just in different ways. This method relies on clever counting and bijections rather than algebraic manipulation.