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:
- First we prove the "base case". That the result holds for $n=1$.
- 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:
- 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
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.
Best Answer
Assume you know it is true up to $k$. For $k \ge 4$ we have $$3^{\frac {k+1}3}=3\cdot 3^{\frac {k-2}3}\ge 3\cdot (k-2)\gt k+1$$