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
Unless I am seriously misunderstanding you, I think your question really amounts to:
"How does mathematical induction work, logically speaking? I don't get it."
That's a perfectly good question to ask. In fact, it is one of the most common questions I have encountered when teaching undergraduate mathematics over the last ten years or so. (Moreover, many students should ask this question, in the sense that they actually don't understand the logic of mathematical induction but either don't perceive their own lack of understanding or are not willing to verbalize it.) It's up there with big conceptual questions like "How does the $\epsilon,\delta$ definition of a limit work, logically speaking?" or "What is uniform convergence, logically speaking?" or "What is linear independence..."
These are key questions, but they are hard to answer in a vacuum. By that I mean that we often build a large portion of an undergraduate course around answering each of the above questions: there are prerequisites, training, several rounds of conceptual explanation of various kinds, examples, exercises, exams, and so forth. Without knowing where you are with respect to all these processes of undergraduate coursework, one (or at least, this one) can't give an explanation tailored to you: one can just try to repeat one of the blanket explanations that one gives in lectures.
So, for instance, I can point you to Chapter 2 of these lecture notes of mine, where induction is explored in great detail.
I can also say that in my department we have decided to place mathematical induction towards the end of an entire course devoted to introducing students to the concepts and methods of mathematical proof. I support that approach, as I have come to realize that induction is more logically complicated than most other proof techniques learned at this level. For instance, I think that in order to properly understand the logic of induction one needs to understand the logic of quantifiers. Thus one version of the Principle of Mathematical Induction is:
Principle of Mathematical Induction for Subsets: Let $S$ be a subset of the positive integers $\mathbb{Z}^+$ satisfying both of the following properties:
(POI1) $1 \in S$.
(POI2) For all $n \in \mathbb{Z}^+$, $n \in S \implies n+1 \in S$.
Then $S = \mathbb{Z}^+$.
My guess is that the place that you should concentrate your efforts is not solely or even primarily in the implication, but rather in understanding the meaning of the universal quantification in (POI2). Notice that that quantification is entirely missing in your description of mathematical induction: that's a symptom of the problem, I suspect.
I am honestly sorry not to be able to give a more useful answer. I have spent 2-3 weeks in undergraduate courses teaching induction and at the end had a substantial minority of the students who were still not fully comfortable with the logic of it. I wish I knew how to do better!
Added: I just clicked on the OP's profile and saw that s/he is 17 years old. Knowing that, I would say -- again, with all possible goodwill and in full knowledge that it could be frustrating to hear it -- to just have a little faith and patience: in my experience, most high school students who grapple with mathematical induction find it just a bit too abstract for them in some (I am imagining!) Piagetian sense. Most of these teenagers find that by the time they are just a year or two older they are simply cognitively more receptive to abstraction in general and mathematical induction in particular. For instance, once in my late 20's I was reminiscing with an old friend from high school who taken most the same (rather advanced, for our tender years and by the standards of our school) math courses as I had, and at one point he vouchsafed to me that he remembered that every once in a while I would say something about "mathematical induction", and that he never knew what the heck I was talking about but kept that to himself. He went on to study electrical engineering at a top American university, and when he saw mathematical induction in his courses then he had no trouble understanding it and was bemused by the silent mental block he had had about it as a high school student.
It may also be the case that high school courses which introduce mathematical induction (at least in the United States) are not very serious about it, do not expect most of the student to really grasp it, and in fact are not giving as good or careful an explanation as one would get in a university course. I learned about mathematical induction while taking a "self-paced precalculus course" over the summer at the age of 15. In self-paced courses, one actually starts at the beginning of the textbook, spends about five hours a day for three weeks reading the textbook, and keeps going until one gets to the end (and demonstrates at least some level of mastery of what was read). This meant that I got exposed to things that it turns out were not actually covered in most high school courses, or certainly not covered very well. Induction was always an "easy sell" for me (somewhat unfortunately, I think, for my current pedagogy), but for instance I remember reading about rotating conic sections to get rid of cross terms like $xy$ and being hella confused about what was going on. Once I learned linear algebra a couple of years later, all that stuff got a lot easier. (But there are still things that I read in my textbooks in that one self-paced course that I have literally never encountered again in 12 more years of schooling and 10 years of post-PhD mathematical research: for instance there is, I vaguely recall, something called a lattus rectum. I am starting to think that it was not actually so important!)
Best Answer
Hint: Stirling's approximation tells you $\log n! = n \log n - n + O(\log n)$ or that $n! \sim \sqrt{n} \left( n / e \right)^n$ where $\sim$ neglects a constant.
Alternatively, assume $n! \in O(2^n)$. Then there would exists a constant $0 < k < \infty$ such that $n! \leq k 2^n$. Show something goes wrong with this for n larger than some $N$ (which is in terms of $k$).