# How to Handle Stronger Induction Hypothesis - Strong Induction

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?

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.

• A question related to "No, not at all: in strong induction you ... from the base case up through some n ...". Agree with this statement, but I usually see proofs describing it without considering the base case, for example: "Assume $P(x)$ holds $\forall x, x\le i$", so strictly speaking this kind of statement is incorrect? (The correct one should change the range to $b\le x\le i$, where $b$ is the base?) Jul 23, 2019 at 8:19
• Nice strong induction example! But BTW here is (IMHO) an even nicer non-induction solution. Model the coins as the vertices of a graph, two vertices adjacent iff the coins are in the same stack. Initially all coins are in one stack so we have the complete graph on $n$ vertices. Splitting into stacks of say $a$ and $b$ coins means removing all the edges between the remaining graphs $K_a$ and $K_b$; the number of edges removed is $ab$, which is the score for this step. Completing the process means removing all $n(n-1)/2$ original edges, so this is the final score. Apr 28 at 7:43
• @David: That is indeed an elegant solution. And a student who looks closely can even see the structure of the strong induction proof in a sense ‘hiding’ in it: it could be recast as essentially the same induction, but in this form we can actually see the inevitable end result without having to go through the induction. Apr 28 at 17:23
• Thanks @Brian! The graph theory solution also makes it clear why the score for a move (in a sense) has to be the product in order for this problem to work. Apr 28 at 22:57