maths.free › Discrete Math & Logic › 5. Sequences › Strong Induction

Strong Induction

Investigation Start with a square piece of paper. You want to cut this square into smaller squares, leaving no waste (every piece of paper you end up with must be a square).

Section Preview

Investigation

Start with a square piece of paper. You want to cut this square into smaller squares, leaving no waste (every piece of paper you end up with must be a square). Obviously it is possible to cut the square into 4 squares. You can also cut it into 9 squares. It turns out you can cut the square into 7 squares (although not all the same size). What other numbers of squares could you end up with?

Sometimes, to prove that \(P(k+1)\) is true, it would be helpful to know that \(P(k)\) and \(P(k-1)\) and \(P(k-2)\) are all true. This is certainly the case when proving something about a recurrence relation that is given as a combination of two previous terms.

Example

Prove that \(2^n\) is a solution to the recurrence relation \(a_n = 5a_{n-1} - 6a_{n-2}\) with initial conditions \(a_0 = 1\) and \(a_1 = 2\).

Solution
Proof

Let \(P(n)\) be the statement, \(a_n = 2^n\). We will show this is true for all \(n \ge 0\).

Base cases: \(a_0 = 2^0 = 1\) and \(a_1 = 2^1 = 2\) both agree with the initial conditions.

Inductive case: Let \(k \ge 2\) be arbitrary. Assume \(P(k)\) and \(P(k-1)\) are both true. That is, assume \(a_k = 2^k\) and \(a_{k-1} = 2^{k-1}\). We will show that \(P(k+1)\) is true. Consider \(a_{k+1}\). We have \[\begin{aligned}a_{k+1} = \amp 5a_k - 6a_{k-1} \\ = \amp 5\cdot 2^k - 6\cdot 2^{k-1} \\ = \amp 10 \cdot 2^{k-1} - 6 \cdot 2^{k-1} \\ = \amp 4\cdot 2^{k-1} \\ = \amp 2^{k+1}\end{aligned}\]. Therefore, by the principle of mathematical induction, \(P(n)\) is true for all \(n \ge 0\).

Well, almost the principle of mathematical induction. Is what we did okay?

There are also times when we might want to go even farther back to use an assumption that \(P(j)\) is true for \(j\) much smaller than \(k+1\). This is the idea behind strong induction and the topic of this short section.

Divide and Conquer

Think of recursive definitions as instructions for building a ladder. You can build the ladder as tall as you like because you have instructions for building the next rung, as long as you are standing on the rung before it.

Induction is the corresponding proof technique. To prove that you can climb the ladder as high as you like, you prove that you can step onto the ladder (the base case) and then prove that, from any rung, you can get to the next rung (the inductive step).

More specifically, suppose you were trying to prove that you can get to rung 4 on the ladder. You have successfully proved that you can get to rung 1, and that from any rung, you can get to the next. So you can get to rung 1, and from 1 you can get to 2. From 2 you can get to 3, and from 3 you can get to 4. Therefore, you can get to 4.

But notice that along the way, you know you have visited rungs 1 through 3. We might as well assume that we have visited all the rungs below the next one we are trying to reach. This is the idea behind strong induction.

A better ladder metaphor for strong induction is to think of ladders as things we can stack on top of each other. We want to argue that it is possible to climb 20 rungs of a ladder. Let's divide that into two smaller ladders, say a 12-rung ladder and an 8-rung ladder. We can assume that we can climb both of these since 20 is the least size we are not yet convinced of. Well, put those two ladders together, and you get \(12+8 = 20\) rungs.

We better climb down from our shaky metaphor before we hurt ourselves. Let's look at a formal definition of strong induction.

Start by saying what we want to prove: Let \(P(n)\) be the statement. Then establish two facts:

  1. Base case: Prove that \(P(0)\) is true. (Perhaps also prove other needed base cases.)

  2. Inductive case: Assume \(P(j)\) is true for all \(j \le k\). Prove that \(P(k+1)\) is true.

Conclude, Therefore, by strong induction, \(P(n)\) is true for all \(n \gt 0\).

Of course, it is acceptable to replace 0 with a larger base case if needed. Technically, strong induction does not require you to prove a separate base case. This is because when proving the inductive case, you must show that \(P(0)\) is true, assuming \(P(k)\) is true for all \(k \lt 0\). But this is not any help so you end up proving \(P(0)\) anyway. To be on the safe side, we will always include the base case separately.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (12)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. True or false: To prove the inductive case of a proof by strong induction, you should assume \(P(k+1)\) is true and prove that \(P(j)\) is true for all \(j \le k\).

  2. Which of the following claims about the relationship between proof by induction and proof by strong induction are true?

  3. What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about after reading this section.

  4. Suppose you are trying to prove, by strong induction, that a statement \(P(n)\) is true for all \(n \ge 0\). What would you attempt to prove in the induction step of the proof? (Select all that apply.)

  5. A simpler version of the chocolate bar problem is as follows: Suppose you have a chocolate bar that is \(n\) squares long. You can break the chocolate bar into two pieces by making a single straight break across the bar. No matter where you make the breaks, you will break the chocolate bar into \(n\) pieces by making \(n-1\) breaks.

    Arrange some of the following statements in the correct order to form a proof of this claim by strong induction.

  6. Suppose a football team only scores 3-point field goals and 7-point touchdowns (ignore the possibilities of safeties, missed extra points, and two-point conversions). Prove, using strong induction, that the team can get any number of points, 12 points or greater.

    အဖြေကို ဖော်ပြပါ

    Hint:

    If you have three base cases, can you always be sure you can get three points more?

  7. Prove using strong induction that the sum of the interior angles of a convex \(n\)-gon is \((n-2)\cdot 180^\circ\). (A convex \(n\)-gon is a polygon with \(n\) sides for which each interior angle is less than \(180^\circ\).)

    အဖြေကို ဖော်ပြပါ

    Hint:

    Start with a \((k+1)\)-gon, and divide it into two smaller polygons.

  8. Prove that every positive integer is either a power of 2 or can be written as the sum of distinct powers of 2.

    အဖြေကို ဖော်ပြပါ

    The proof will be by strong induction.

    Proof

    Let \(P(n)\) be the statement, \(n\) is either a power of 2 or can be written as the sum of distinct powers of 2. We will show that \(P(n)\) is true for all \(n \ge 1\).

    Base case: \(1 = 2^0\) is a power of 2, so \(P(1)\) is true.

    Inductive case: Suppose \(P(k)\) is true for all \(k \lt n\). Now if \(n\) is a power of 2, we are done. If not, let \(2^x\) be the largest power of 2 strictly less than \(n\). Consider \(n - 2^x\), which is a smaller number, in fact smaller than both \(n\) and \(2^x\). Thus \(n-2^x\) is either a power of 2 or can be written as the sum of distinct powers of 2, but none of them are going to be \(2^x\), so together with \(2^x\) we have written \(n\) as the sum of distinct powers of 2.

    Therefore, by the principle of (strong) mathematical induction, \(P(n)\) is true for all \(n \ge 1\).

  9. Prove, using strong induction, that every natural number is either a Fibonacci number or can be written as the sum of distinct Fibonacci numbers.

    အဖြေကို ဖော်ပြပါ

    Hint:

    As with the previous question, we will want to subtract something from \(n\) in the inductive step. There we subtracted the largest power of 2 less than \(n\). So what should you subtract here?

    Note that you will still need to take care here that the sum you get from the inductive hypothesis, together with the number you subtracted, will be a sum of distinct Fibonacci numbers. In fact, you could prove that the Fibonacci numbers in the sum are non-consecutive!

  10. We have previously proved that for any tree, the number of edges is always one less than the number of vertices. That is, a tree with \(v\) vertices and \(e\) edges satisfies \(v = e+1\).

    Give an alternate proof of this fact using strong induction on the number of vertices. Do so by taking a non-leaf vertex and splitting it into two vertices, each belonging to a separate tree.

  11. Suppose that a particular real number \(x\) has the property that \(x + \frac{1}{x}\) is an integer. Prove that \(x^n + \frac{1}{x^n}\) is an integer for all natural numbers \(n\).

    အဖြေကို ဖော်ပြပါ

    Hint:

    You will need to use strong induction. For the inductive case, try multiplying \(\left (x^k + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right)\), and collect which terms together are integers.

  12. Given a square, you can cut the square into smaller squares by cutting along lines parallel to the sides of the original square (these lines do not need to travel the entire side length of the original square). For example, by cutting along the lines below, you will divide a square into 6 smaller squares:

    Prove, using strong induction, that it is possible to cut a square into \(n\) smaller squares for any \(n \ge 6\).

    အဖြေကို ဖော်ပြပါ

    Hint:

    You will need three base cases. This is a very good hint actually, as it suggests that to prove \(P(n)\) is true, you would want to use the fact that \(P(n-3)\) is true. So somehow you need to increase the number of squares by 3.

Symbols used here

P(A),\ P(A \mid B)
probability, conditional probability
Chance of A; chance of A given that B happened.
^\circ
degrees
1/360 of a full turn. 180° = π radians.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

How to: Strong Induction

  1. Explain the difference between proof by induction and proof by strong induction.
  2. Use strong induction to prove statements.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

သင့်ရဲ့ကိုယ်ပိုင်စမ်းသပ်

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

ပိုပြီး Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions