4
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

Reset to default
7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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?) $\endgroup$
    – linear_combinatori_probabi
    Jul 23, 2019 at 8:19
  • $\begingroup$ 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. $\endgroup$
    – David
    Apr 28, 2022 at 7:43
  • $\begingroup$ @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. $\endgroup$
    – Brian M. Scott
    Apr 28, 2022 at 17:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – David
    Apr 28, 2022 at 22:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .