Solving Recurrence Relations with Strong Induction

In our previous lesson, we established the principle of mathematical induction, which allows us to prove statements for an infinite number of cases by checking a base case and proving that if one case holds, the next one must follow. This "domino effect" is a cornerstone of mathematical proof.

Today, we will enhance this powerful tool by learning about strong induction. You'll discover that for some problems, particularly those involving sequences defined by recurrence relations, assuming only the immediately preceding case ( $P (k)$ ) is not enough. Strong induction gives us a "stronger" hypothesis: we assume the statement holds for all cases up to $k$ . This will equip you to prove properties of recursively defined sequences, a common feature in advanced combinatorics and a key step toward your goal of solving Olympiad-level problems.

When One Domino Isn't Enough

Recall the domino analogy from our last lesson: to know all dominoes will fall, you just need to know the first one falls and that any domino ( $k$ ) will knock over its immediate successor ( $k + 1$ ).

But what if the dominoes were set up differently? Imagine that for domino $k + 1$ to fall, it needs to be hit by both domino $k$ and domino $k - 1$ . In this scenario, just knowing that domino $k$ has fallen isn't enough to guarantee the chain reaction continues. You need to know that all the preceding dominoes have fallen to be sure you have the necessary ones to topple the next. This is the intuitive idea behind strong induction.

Let's formalize this by examining the structure of a proof by strong induction.

4.6 Strong Induction - Discrete Mathematics

This resource formally defines the structure of a strong induction proof and contrasts it with the standard induction we've already learned.

Please read the summary box titled "Strong Induction Proof Structure." Pay close attention to the Inductive case. Notice how the assumption is different from what we used in the previous lesson. Instead of assuming only P(k) is true, we now assume P(j) is true for all j \le k.

The Structure and Power of Strong Induction

As you've just read, the key difference lies in the inductive hypothesis.

Standard Induction Hypothesis: Assume $P (k)$ is true.
Strong Induction Hypothesis: Assume $P (j)$ is true for all integers $j$ from the base case up to $k$ .

It might seem like we are assuming more, which is why it's called "strong" induction. However, the two principles are logically equivalent. Anything provable with one can be proven with the other. The real benefit of strong induction is not one of logical power, but of practical convenience for certain types of problems.

The following video provides an excellent walkthrough of this concept and why the expanded assumption is so helpful.

Proof by Strong Induction (full lecture)

This video, by Dr. Valerie Hower, explains the logic of strong induction and highlights the difference in the inductive hypothesis.

Please watch from the beginning of the section on strong induction. The lecturer clearly articulates how the inductive hypothesis changes from assuming s(k) to assuming s(1) and s(2) and ... and s(k).

Application: Recursively Defined Sequences

The primary arena where strong induction shines is in proving properties of recursively defined sequences (also called recurrence relations). These are sequences where each term is defined by one or more preceding terms.

You are already familiar with the most famous example, the Fibonacci sequence: $F_{n} = F_{n - 1} + F_{n - 2}$ , with initial values $F_{0} = 0, F_{1} = 1$ . To prove something about $F_{k + 1}$ , the definition itself forces us to look at both $F_{k}$ and $F_{k - 1}$ . Standard induction, which only gives us an assumption about the $k$ -th term, would leave us unable to say anything about the $(k - 1)$ -th term. Strong induction elegantly solves this by letting us assume the property holds for both.

A crucial point arises here: if your recurrence relation depends on the two previous terms, you will generally need to prove two base cases to get the induction started. If it depends on three previous terms, you'll need three base cases, and so on.

Let's see this in action with a complete example.

Proof by Strong Induction (full lecture)

This segment of the lecture demonstrates a full proof by strong induction for a recursively defined sequence. Crucially, it shows how the structure of the recurrence dictates the number of base cases you need to verify.

Watch the example that begins at the start of the example. Pay close attention to how the recurrence f(n) = 2f(n-1) - f(n-2) requires stepping back two terms, which in turn means two base cases (f(1) and f(2)) must be checked.

To reinforce this process, let's walk through another example in text.

Example: Proving a Closed Form for a Sequence

Consider a sequence $s_{n}$ defined as follows:

$s_{0} = 0$ , $s_{1} = 4$
$s_{k} = 6 s_{k - 1} - 5 s_{k - 2}$ for all integers $k \geq 2$ .

Let's prove that the closed-form formula for this sequence is $s_{n} = 5^{n} - 1$ for all $n \geq 0$ .

Proof:
Let $P (n)$ be the statement $s_{n} = 5^{n} - 1$ .

Base Cases: The recurrence depends on two previous terms ( $s_{k - 1}$ and $s_{k - 2}$ ), so we must verify two base cases, $n = 0$ and $n = 1$ .
- For $n = 0$ : $s_{0} = 0$ . The formula gives $5^{0} - 1 = 1 - 1 = 0$ . So $P (0)$ is true.
- For $n = 1$ : $s_{1} = 4$ . The formula gives $5^{1} - 1 = 5 - 1 = 4$ . So $P (1)$ is true.
Inductive Step:
- Inductive Hypothesis: Assume for an integer $k \geq 1$ that $P (j)$ is true for all integers $j$ such that $0 \leq j \leq k$ . That is, we assume $s_{j} = 5^{j} - 1$ for all $0 \leq j \leq k$ .
- Goal: We want to prove $P (k + 1)$ is true, i.e., $s_{k + 1} = 5^{k + 1} - 1$ .
Since $k \geq 1$ , it follows that $k + 1 \geq 2$ . Thus, we can use the recurrence relation to express $s_{k + 1}$ :
$s_{k + 1} = 6 s_{k} - 5 s_{k - 1}$
Since both $k$ and $k - 1$ are within the range $[0, k]$ , we can apply our inductive hypothesis to both $s_{k}$ and $s_{k - 1}$ :
$s_{k + 1} = 6 (5^{k} - 1) - 5 (5^{k - 1} - 1)$
Now we use algebra to simplify:
$s_{k + 1} = 6 \cdot 5^{k} - 6 - 5 \cdot 5^{k - 1} + 5$ $s_{k + 1} = 6 \cdot 5^{k} - 5^{k} - 1$ $s_{k + 1} = (6 - 1) \cdot 5^{k} - 1$ $s_{k + 1} = 5 \cdot 5^{k} - 1 = 5^{k + 1} - 1$
This is exactly $P (k + 1)$ .

Therefore, by the principle of strong induction, $s_{n} = 5^{n} - 1$ is true for all integers $n \geq 0$ . This full example is also covered in the "Sequences and Mathematical Induction" slides on pages 44-46.

Practice Problems

Now it's your turn to build your skills. These problems are designed to give you practice with strong induction, connecting to your interest in number theory and Olympiad-style questions.

A Fibonacci Identity: Let $F_{n}$ be the Fibonacci sequence, where $F_{0} = 0, F_{1} = 1$ , and $F_{n} = F_{n - 1} + F_{n - 2}$ for $n \geq 2$ . Prove Cassini's Identity for all $n \geq 1$ :
$F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$
Hint: This doesn't look like a typical induction problem at first. Try to show that $P (k)$ and $P (k - 1)$ together can be used to prove $P (k + 1)$ . You will need to use the Fibonacci recurrence relation multiple times.
Fundamental Theorem of Arithmetic: You're comfortable with number theory, so let's prove a foundational result. Prove that any integer $n > 1$ is either a prime number or can be written as a product of prime numbers.
Hint: In your inductive step, consider the two cases for $k + 1$ : it is either prime (in which case you're done) or composite. If it's composite, what does the strong induction hypothesis tell you about its factors?
An Olympiad-Style Problem: Let $x$ be a real number such that $x + \frac{1}{x}$ is an integer. Prove using strong induction that $x^{n} + \frac{1}{x ^{n}}$ is also an integer for all positive integers $n$ .
Hint: For the inductive step, consider the product $(x^{k} + \frac{1}{x ^{k}}) (x + \frac{1}{x})$ . Expand it and see how you can use your strong inductive hypothesis for both the $k$ and $k - 1$ cases to prove the $(k + 1)$ case.
A Custom Recurrence: Let a sequence be defined by $a_{0} = 2, a_{1} = 1$ , and $a_{n} = a_{n - 1} + 2 a_{n - 2}$ for $n \geq 2$ . Prove that $a_{n} = 2^{n - 1} + (- 1)^{n}$ for all $n \geq 0$ .

Conclusion

In this lesson, you've added strong induction to your proof-writing arsenal. You've seen that while it is logically equivalent to standard induction, it is far more convenient for proofs involving recurrence relations, where the state of a future term depends on multiple past terms.

Key Takeaways:

Strong Induction Hypothesis: To prove $P (k + 1)$ , you assume $P (j)$ is true for all cases from the beginning up to $j = k$ .
When to Use It: Strong induction is the natural choice for problems involving recursively defined sequences, or any problem where the $k + 1$ case relies on a case earlier than $k$ .
Base Cases: The number of terms the recurrence "looks back" is a strong guide to how many base cases you need to establish manually before the induction can take over.

We are steadily building the foundational tools you'll need for your Olympiad journey. In the next lesson, we will switch gears to another fundamental proof technique: proof by contradiction. This method is incredibly powerful for showing that certain combinatorial arrangements are impossible.

Recommended resources

When One Domino Isn't Enough

The Structure and Power of Strong Induction

Application: Recursively Defined Sequences

Practice Problems

Conclusion