[Math] How to Handle Stronger Induction Hypothesis – Strong Induction

discrete mathematicsinduction

I'm having trouble understanding strong induction proofs

I understand how to do ordinary induction proofs and I understand that strong induction proofs are the same as ordinary with the exception that you have to assume that the theorem holds for all numbers up to and including some $n$ (starting at the base case) then we try and show: theorem holds for $n+1$.

How do you show this exactly.

Here is a proof by induction:

Thm: $n≥1, 1+6+11+16+\dots+(5n-4) = (n(5n-3))/2$

Proof (by induction)

Basis step: for $n=1: 5-4=(5-3)/2 \Rightarrow 1=1$.
The basis step holds

Induction Step:
Suppose that for some integer $k≥1$,
$$
1+6+11+16+…+(5k-4) = \frac{k(5k-3)}{2} \qquad\text{(inductive hypothesis)}
$$

Want to show:
$$
1+6+11+16+…+(5k-4)+(5(k+1)-4) = \frac{(k+1)(5(k+1)-3)}{2}
$$
so
$$
\frac{k(5k-3)}{2} + (5(k+1)-4) = \frac{(k+1)(5(k+1)-3)}{2}
$$

then you just show that they are equal.

So how can I do the same proof using strong induction?
What are the things I need to add/change in order for this proof to be a strong induction proof?

Best Answer

You wrote:

i understand how to do ordinary induction proofs and i understand that strong induction proofs are the same as ordinary with the exception that you have to show that the theorem holds for all numbers up to and including some n (starting at the base case) then we try and show: theorem holds for $n+1$

No, not at all: in strong induction you assume as your induction hypothesis that the theorem holds for all numbers from the base case up through some $n$ and try to show that it holds for $n+1$; you don’t try to prove the induction hypothesis.

In your example the simple induction hypothesis that the result is true for $n$ is already enough to let you prove that it’s true for $n+1$, so there’s neither need nor reason to use a stronger induction hypothesis. The proof by ordinary induction can be seen as a proof by strong induction in which you simply didn’t use most of the induction hypothesis.

I suggest that you read this question and my answer to it and see whether that clears up some of your confusion; at worst it may help you to pinpoint exactly where you’re having trouble.

Added: Here’s an example of an argument that really does want strong induction. Consider the following solitaire ‘game’. You start with a stack of $n$ pennies. At each move you pick a stack that has at least two pennies in it and split it into two non-empty stacks; your score for that move is the product of the numbers of pennies in the two stacks. Thus, if you split a stack of $10$ pennies into a stack of $3$ and a stack of $7$, you get $3\cdot7=21$ points. The game is over when you have $n$ stacks of one penny each.

Claim: No matter how you play, your total score at the end of the game will be $\frac12n(n-1)$.

If $n=1$, you can’t make any move at all, so your final score is $0=\frac12\cdot1\cdot0$, so the theorem is certainly true for $n=1$. Now suppose that $n>1$ and the theorem is true for all positive integers $m<n$. (This is the strong induction hypothesis.) You make your first move; say that you divide the pile into a pile of $m$ pennies and another pile of $n-m$ pennies, scoring $m(n-m)$ points. You can now think of the rest of the game as splitting into a pair of subgames, one starting with $m$ pennies, the other with $n-m$.

Since $m<n$, by the induction hypothesis you’ll get $\frac12m(m-1)$ points from the first subgame. Similarly, $n-m<n$, so by the induction hypothesis you’ll get $\frac12(n-m)(n-m-1)$ points from the second subgame. (Note that the two subgames really do proceed independently: the piles that you create in one have no influence on what you can do in the other.)

Your total score is therefore going to be

$$m(n-m)+\frac12m(m-1)+\frac12(n-m)(n-m-1)\;,$$

which (after a bit of algebra) simplifies to $\frac12n(n-1)$, as desired, and the result follows by (strong) induction.

Related Question