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
For example above, the question is asking you determine which amounts of postage can be formed using $4$-cent and $5$-cent stamps. Such that we know $4,5,8,9,10,12,13,14,15, \ldots$ can be formed using just $4$ cent and $5$ cent. Why for basis are we just using $12-15$ instead of using $4-9$?
This problem appears to be taken from Kenneth H. Rosen's text Discrete Mathematics and its Applications.
You have misstated the question in the example. What we need to prove is that every amount of postage of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps.
By showing that the four consecutive amounts $12$ cents, $13$ cents, $14$ cents, and $15$ cents can be formed using just $4$-cent and $5$-cent stamps, Rosen is providing a basis step for his strong induction argument that all amounts of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps. He wants to show that for $n \geq 16$ that since $n - 4 = 4j + 5k$ for some positive integers $j$ and $k$, then $n = 4(j + 1) + 5k$. Together with his demonstration that the amounts $12$ cents, $13$ cents, $14$ cents, and $15$ cents can be formed using only $4$-cent and $5$-cent stamps, this proves that all amounts of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps.
The reason Rosen starts at $12$ cents is that $12$ cents, $13$ cents, $14$ cents, and $15$ cents are the first four consecutive amounts that can be formed using only $4$-cent and $5$-cent stamps as it is not possible to form $11$ cents using only $4$-cent and $5$-cent stamps. Notice that the argument that if $n - 4 = 4j + 5k$ for some positive integers $j$ and $k$, then $n = 4(j + 1) + k$ cannot be applied when $n = 15$ since no such positive integers $j$ and $k$ exist for $n - 4 = 15 - 4 = 11$.
This is an example of the Frobenius coin problem. The English mathematician James Joseph Sylvester showed that the largest amount that cannot be formed using only $m$-cent and $n$-cent stamps with $\gcd(m, n) = 1$ is $mn - m - n$ cents. The number $mn - m - n$ is called the Frobenius number.
In our case, $m = 4$ and $n = 5$, so the largest amount that cannot be formed using only $4$-cent and $5$-cent stamps is $4 \cdot 5 - 4 - 5 = 11$ cents.
Same here, we know that $4, 8, 11, 12, 15, 16, 19, 20, 22, 23, 24, 26, 27, 28, \ldots$ can be formed using $4$-cent and $11$-cent stamps. Why do we want to prove $P(n)$ is true for all $n \geq 30$? I don't understand how to find the $j$ and $k$ (The Second Principle of Mathematical Induction: if (i) $P(a)$ is true for the starting point $a \in \mathbb{Z}^{+}$, and (ii) (for any $k \in \mathbb{Z}^{+}$) if $P(j)$ is true for any $j \in \mathbb{Z}^{+}$ such that $a \leq j \leq k$, then $P(k+1)$ is true, then $P(n)$ is true for all $n \in \mathbb{Z}^{+}, n \geq a$)?
We want to prove $P(n)$ holds for $n \geq 30$ since it is not possible to form $4 \cdot 11 - 4 - 11 = 29$ cents using only $4$-cent and $11$-cent stamps.
Observe that
\begin{align*}
30 & = 2 \cdot 4 + 2 \cdot 11\\
31 & = (2 + 3) \cdot 4 + 1 \cdot 11\\
& = 5 \cdot 4 + 1 \cdot 11\\
32 & = (5 + 3) \cdot 4 + 0 \cdot 11\\
& = 8 \cdot 4 + 0 \cdot 11\\
33 & = (8 - 8) \cdot 4 + 3 \cdot 11\\
& = 0 \cdot 4 + 3 \cdot 11\\
\end{align*}
Notice that in increasing from $n$ to $n + 1$, we either replace an $11$ by three $4$'s or we replace eight $4$'s with three $11$'s.
For $n \geq 30$, if
- $n = 4j + 11k$ and $k > 0$, then $n + 1 = 4(j + 3) + 11(k - 1)$
- $n = 4j + 11k$ and $k = 0$, then $j \geq 8$, so $n + 1 = 4(j - 8) + 11 \cdot 3$
Best Answer
For each $n\geq 0$, let $S(n)$ denote the statement $$ S(n) : F_n+2F_{n+1}=F_{n+3}. $$ First note that $S(n)$ has a rather trivial direct proof: $$ F_{n+3} = F_{n+1}+F_{n+2} = F_{n+1}+(F_n+F_{n+1})=F_n+2F_{n+1}. $$ Thus, it is really not necessary to prove your statement by using induction, but let's do it anyway since we're on the topic.
Base step: $S(0)$ says $F_0+2F_1=F_3$, which is true since $F_0=0, F_1=1$, and $F_3=2$.
Inductive step: For some fixed $k\geq 0$, assume that $S(k)$ is true. To be shown is that $$ S(k+1) : F_{k+1}+2F_{k+2} = F_{k+4} $$ follows from $S(k)$. Note that $S(k+1)$ can be proved without the inductive hypothesis; however, to formulate the proof as an inductive proof, following sequence of equalities uses the inductive hypothesis: \begin{align} F_{k+1}+2F_{k+2} &= F_{k+1}+2(F_k+F_{k+1})\\[0.5em] &= (F_{k+1}+F_k)+(F_k+2F_{k+1})\\[0.5em] &= F_{k+2}+(F_k+2F_{k+1})\\[0.5em] &= F_{k+2}+F_{k+3}\qquad\text{by $S(k)$}\\[0.5em] &= F_{k+4}. \end{align} This completes the inductive step $S(k)\to S(k+1)$.
Thus, by mathematical induction, $S(n)$ is true for every $n\geq 0$. $\Box$