1
$\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?

  • 0
    I think this is the third question on strong induction in the last 24 hours. Is there a sale on?2012-12-11

1 Answers 1

5

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

Since $m

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.

  • 0
    right sorry about that, assume instead of show is correct. but the reason why i want to see this proof done in strong induction is to understand how it works, i know how to prove it using ordinary induction but im still unclear how to do it using strong induction (basically i dont know how to prove thms using strong induction)2012-12-11
  • 0
    @cloud9resident: You **did** prove it by strong induction: in this case there’s absolutely no difference in the arguments. Let me see if I can come up with an example that really does use strong induction.2012-12-11
  • 0
    ohhh lol, so since this is an easy example it can be proved using ordinary induction, where as examples that can't be proved using ordinary induction have to use strong induction, right?2012-12-11
  • 0
    @cloud9resident: Right. As I said in the other answer, you use as much of the full strength of the strong induction hypothesis as you need; if that’s just $P(n)$, you end up doing ordinary induction. A lot of basic results about the Fibonacci numbers require the induction hypothesis for $n$ and $n-1$, though not for all of the numbers before that.2012-12-11
  • 0
    here is an example http://www.math.sc.edu/~girardi/m5545/hwsoln/pmiFibExSolnF10.pdf this however is super convoluted. First where did they even get Fn ≤ r^(n-1)?2012-12-11
  • 0
    and second [r+1] = [r^2] ????2012-12-11
  • 0
    @cloud9resident: Take a look at the computationally simpler example that I just added. It’s a better example anyway, since it really does have to use **all** of the earlier cases; the one that you found is computationally messier and uses only the two previous cases.2012-12-11
  • 0
    i dont understand how you got (1/2)m(m−1) and (1/2)(n−m)(n−m−1) points for the second two subgames?2012-12-11
  • 0
    @cloud9resident: The formula to be proved says that the total number of points is $$\frac12\cdot(\text{number of pennies})\cdot(\text{number of pennies }-1)\;,$$ and the induction hypothesis is that this formula is correct for any number of pennies less than $n$. Since $m$ and $n-m$ are less than $n$, it holds for them. In the first case $\text{number of pennies}=m$, and in the other case it’s $n-m$.2012-12-11
  • 0
    so in this case n+1 is not needed?2012-12-11
  • 1
    @cloud9resident: It’s a matter of taste whether you assume $P(m)$ for $m and prove $P(n)$ or assume $P(m)$ for $m\le n$ and prove $P(n+1)$, just as in ordinary induction it’s a matter of taste whether you assume $P(n-1)$ and prove $P(n)$ or assume $P(n)$ and prove $P(n+1)$. In each case the logic is identical: you’ve just named the indices a little differently.2012-12-11