Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to understand this example of strong induction. I know normal induction. In normal induction, if base case is true then we assume some number $n$ to be true. Afterwards, we prove $n+1$ is true.

In strong induction, as you can see below, you prove more than 1 base case. I am not sure why. Then you prove $n+1$ is true...

I don't know why or how they choose however many base cases to prove or why proving extra base cases matters. Could someone please explain the inductive step of $3 + n - 2$? Where did it come from?

enter image description here

enter image description here

share|improve this question

2 Answers 2

up vote 7 down vote accepted

Arturo's answer is very correct, but since you said you haven't understand much, I will just try to rephrase some points.

First, it's important to notice that as it is, the proof (or the statement is wrong). The correct statement is, as stated by Arturo:

An n-cent postage where n is greater or equal than 12 can be made up using 3-cents and 7 -cents stamps.

It's actually quite simple to see that it is not true for any n, for instance, you can't make up a 2-cents postage with only 3-cents and 7-cents stamps. So the base case (where the induction can start) will be n=12, and not n=0 or n=1. You can prove the base case by showing that 12 = 3 + 3 + 3 + 3.

Now, you could try to use simple induction, and to say let's assume P(n) is true, and let's show that P(n+1) is also true. The problem is that you won't be able to show that, because knowing how to make a n-cent postage with 3-cents and 7-cents stamps does not help you to make a n+1-cent postage! For instance, a 20-cents postage can be made as 7+3+7+3. But a 21-cents postage is made using 7+7+7.

In other words, you can't reuse P(n) in order to prove P(n+1).

However, you can see that if you know how to make a n-cent postage, you also know how to make a n+3-cent postage, because it's enough to take the n-cents postage, and to add a 3-cents stamp. So, if you know P(n), then you can also prove P(n+3).

Intuitively, the problem is that because you need to make a step of 3 instead of 1, then you need to prove the base case for B, B+1 and B+2, where B is your starting value, that is, B=12 in this case. So, you need to show that P holds for 12, 13 and 14, which is the case.

Now, your proof holds, because intuitively:

  • it holds for 12, as showed
  • it holds for 13, as showed
  • it holds for 14, as showed,
  • it holds for 15, because it holds for 12, and if it holds for N, it also holds for N+3
  • it holds for 16, because it holds for 13, and if it holds for N, it also holds for N+3
  • it holds for 17, because it holds for 14, and if it holds for N, it also holds for N+3
  • it holds for 18, because it holds for 15, and if it holds for N, it also holds for N+3
  • etc

So, I'd say that in this case, you use the strong induction because you can't use the simple induction, as you would be unable to prove the simple induction step. I hope it clarifies things a bit.

share|improve this answer
    
ahhhh I got it! so what you are saying is that there is no "fixed" formula that will prove if it works for n then it works for n+1 so we must make a chained link or rather a starting position where the previous number (-3 the n) becomes n and the current value becomes n+3.....so genuinely our current basis step doesnt work because u cant prove this for 11 but u can for 10 or 9 but since 11 doesnt work and many other below 12 dont we must build our own basis terms to start the chain reaction... 12 is not enough as it doesnt cover for all the forward terms so we must come up with some of our own –  Raynos Jan 30 '12 at 3:31
    
So basically they got rid of the odd even issue caused between 7 and 3 by creating a dominoe effect and saying if a n cent stamp can be made up then a n+ (using 3 cent stamp) we can make up the n+3 cent stamp...i understand it sooo clearly now. took lots sitting and thinking..math is so fun when you understand it but total nutcase when it makes no sense...discrete math certainly requires a different perspective –  Raynos Jan 30 '12 at 4:16

In normal induction we proved that if base case is true then we assume some number n to be true then we prove n+1 is true.

As written, this is inaccurate, though that may be simply a result of poor phrasing.

In standard induction, we do two things:

  1. First we prove the "base case". That the result holds for $n=1$.
  2. Then we prove that for every positive integer $n$, if the result holds for $n$, then it also holds for $n+1$.

(This is different from what you wrote; what you wrote is that one proves that if the result holds for $1$, then if it holds for some $n$, then it holds for $n+1$.)

In strong induction, we only need to prove one thing:

  1. For every positive integer $n$, if the result holds for all positive integers $k\lt n$, then the result holds for $n$.

This is enough to establish the result holds for all positive integer: if the result does not hold for all positive integers, then it fails to hold for some. Take the smallest integer $n$ for which the result does not hold. Then it holds for all strictly smaller integers; but by the implication above, this would imply that it holds for $n$ as well, a contradiction. So it holds for all positive integers.

(I used what is called the "Well Ordering Principle for Positive Integers": every nonempty collection of positive integers has a smallest element; this is in fact equivalent to induction).

Caveat: In strong induction, it is often the case that the general argument proving the implication does not hold for all $n$, but only for all "sufficiently large" $n$. In that case, we need to establish the implication for some $n$ "by hand". This is often, incorrectly, called a "base" of the induction. In fact, it is a "special case" of the proof of the single inductive step.

Here, the proposition being proven is:

Either $n\lt 12$, or else an $n$ cent stamp can be made using only $3$- and $7$-cent stamps.

The strong inductive step is:

Assume that the result is true for all $k$ strictly smaller than $n$. Then it holds for $n-3$; we can make an $n-3$-cent stamp using $3$- and $7$-cent stamps. Then we can make an $n$-cent stamp by making an $n-3$-cent stamp, and adding a $3$-cent stamp. So we can make an $n$-cent stamp. QED

The problem is that this argument works if $n$ is "sufficiently large", but it does not work if $n\lt 12$ (because that is not what we need to prove for $n\lt 12$) and it does not work if $n=12$, $n=13$, or $n=14$, because then $n-3\lt 12$, so our inductive hypothesis does not guarantee that we can make an $n-3$-cent stamp (the proposition "works" for any $n\lt 12$ by default). So the argument above is not complete. We still need to make sure everything works for $n\lt 12$, $n=12$, $n=13$, and $n=14$. By "everything works", we mean "if the proposition is true for all $k$ strictly smaller than $n$, then it holds for $n$.

If $n\lt 12$, then this is true simply because the proposition is true for $n$, so the consequent is true.

If $n=12$, this is true because we can verify that we can make a $12$-cent stamp (four $3$-cent stamps). So the implication is true because the consequent is true.

If $n=13$, the implication is true because the consequent is true: we can make a $13$-cent stamp (a $7$-cent stamp and two $3$-cent stamps).

If $n=14$, the implication is true because the consequent is true: we can make a $14-$cent stamp (two $7$-cent stamps).

And if $n\geq 15$, the argument we had before already worked.

So now we have established the strong inductive step for every positive integer $n$, and so by strong induction we have established the desired proposition for all positive integers.

(The $3+n-2$ came from applying the inductive argument to $n+1$).


Personally, I prefer to do proofs by strong induction by first doing the "general case", and then doing the "special cases", as the latter are only revealed after we examine the general proof and see if it works for all $n$ or not. This also helps draw the distinction between proofs by strong induction and proofs by regular induction, specifically that the latter need a base and an inductive step, while the former only needs an inductive step (but may require special cases).

Added. See also this previous question

share|improve this answer
    
<3 Arturo thank you for putting so much time and effort into helping me –  Raynos Jan 25 '12 at 5:52
    
I didnt really understand much of what u said perhaps because I am not very used to the consequent or implication terms. I just started this discrete math course and the concepts are hard to absorb mainly because I have never thought in such a way. I will give a try to the previous question you posted to see if it helps. –  Raynos Jan 25 '12 at 6:14
1  
@Raynos: An implication is a statement of the form "if $P$, then $Q$". $P$ is called the "antecedent" of the implication, $Q$ is called the "consequent" of the implication. The only time that an implication is false is when the antecedent ($P$) is true and the consequent ($Q$) is false. So, in an implication, if the antecedent is (always) false, then the implication is (always) true; and if the consequent is true, then the implication is true. ("False implies anything" and "Anything implies truth"). –  Arturo Magidin Jan 25 '12 at 6:19
    
@Raynos: PS If you didn't really understand much of what I wrote, then don't accept the answer yet! Ask questions, and also wait and see if others offer you alternative answers that you do understand. By accepting an answer, you are discouraging others (though, of course, not preventing them) form answering your question. –  Arturo Magidin Jan 25 '12 at 6:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.