I understand the principle of finite induction, but my book then mentions that there is a variant of the first where requirement b is changed to
If $k$ is a positive integer such that $1,2, \dots, k$ belong to $S$, then $k + 1$ must also be in $S$.
The sample problem is proving that the inequality about the Lucas numbers
$l_n < (7/4)^n$.
I understand the algebra of the proof, but I do no understand how it uses the second principle or how it is different from the first principle?
The proof for the lucas numbers
$$
a_1 = 1 < \left(\frac{7}{4}\right)^1 = \frac{7}{4}\text{ and }a_2 = 3 \lt \left(\frac{7}{4}\right)^2 = \frac{49}{16}.$$
Choose an integer $k\geq 3$ and assume that the inequality is valid for $n = 1,2,\ldots,k$. Then
$$a_{k-1} \lt \left(\frac{7}{4}\right)^{k-1}\text{ and }a_{k-2} \lt \left(\frac{7}{4}\right)^{k-2},$$
so
\begin{align*}
a_k &= a_{k-1} + a_{k-2}\\\
&\lt \left(\frac{7}{4}\right)^{k-1} + \left(\frac{7}{4}\right)^{k-2}\\\
&= \left(\frac{7}{4}\right)^{k-2}\left(\frac{7}{4} + 1\right)\\\
&= \left(\frac{7}{4}\right)^{k-2}\left(\frac{11}{4}\right)\\\
&\lt \left(\frac{7}{4}\right)^{k-2}\left(\frac{7}{4}\right)^2\\\
&= \left(\frac{7}{4}\right)^k
\end{align*}
The responses are all helpful, but if someone could point out what the difference is when you go about actually using strong induction instead of weak induction. (You could use the lucas number proof or something else)
Best Answer
There are two basic differences:
In ordinary induction, we need a base case (proving it for $k=1$; that is, proving that $1\in S$); in the second principle of induction (also called "strong induction") you do not need a base case (but see the caveat below).
In ordinary induction, the "Induction Hypothesis" is that the $k\in S$; in the second principle, the "Induction Hypothesis" is that all the natural numbers strictly less than $k+1$ are in $S$.
For example, if you want to prove that every positive integer can be factored into primes, if you use ordinary induction you would have to first show that $1$ can be factored into primes, and then you would show that if $k$ can be factored into primes, then $k+1$ can be factored into primes. This is actually pretty hard to do, because the factorization of $k+1$ has little or nothing to do with the factorization of $k$. This is a very difficult proposition to prove directly using ordinary induction.
If you wanted to prove the same proposition using the second principle of induction, you would instead assume that all numbers strictly less than $k$ can be factored into primes, and try to show from this assumption that $k$ can be factored into primes (which is much simpler: if $k=1$ or $k$ is prime, there is nothing to do; otherwise, you can write $k=ab$, each $a$ or $b$ strictly smaller than $k$ and greater than $1$, so you can apply the induction hypothesis to both to get a factorization).
In other words, in the second principle, you get to assume more in the inductive step.
Caveat: Formally, the second principle does not require a base; this is because if you can actually prove that "if all positive integers strictly smaller than $k$ are in $S$ then $k$ is in $S$", then for $k=1$ the premise is vacuously true (all positive integer smaller than $1$ are in $S$, because there is no such number at all), so the implication would yield that $k=1$ must also be in $S$. However, in most actual applications, the inductive argument does not work for $k=1$ (or for other special cases), so that these have to be proven separately. They amount to "special cases" instead of "bases".
In fact, both principles are equivalent for the positive integers. That is, if you can do a proof using ordinary induction, then you can translate that into a proof using the second induction principle in a fairly mechanical manner. And if you can do a proof using the second induction principle, you can transform that into a proof using the first induction principle (though in an indirect manner), again in a fairly mechanical way (provided you take for granted some properties of the positive integers; for example, that every positive integer is either equal to $1$, or else is $k+1$ for some positive integer $k$).
Note: The reason the second principle is called "strong induction" is that you can use it in other contexts to prove more than ordinary induction would. For example, imagine a situation in which you have a set $T$ that consists of two copies of the integers: a blue copy and a green copy, with the blue copy going "first". If you prove that $S$ is a subset of $T$ such that blue $1$ is in $S$, and whenever $k$ ($k$ either a blue positive integer or a green positive integer) is in $S$ then $k+1$ is in $S$ (ordinary induction), then you can conclude that all blue integers are in $S$, but the argument by itself does not tell you whether there are any green integers in $S$ (you would have to separately prove that green-$1$ is in $S$). But if you use strong induction, and prove that whenever all integers, blue or green, that are strictly smaller than $k$ are in $S$ then $k$ is in $S$, then you can conclude that $S$ will contain all blue integers and all green integers too. So you can actually get a stronger conclusion from using strong induction.
Caveat the Second: Special cases show up far more often in proofs using strong induction than in proofs using ordinary induction, but they sometimes occur in the latter as well. As a famous example of a "proof" using regular induction that would require a special case (and that in fact is false because that special case fails) is the fake proof of the proposition that "If, in a group of people, at least one of them has blue eyes, then everyone in the group has blue eyes." The proof is as follows: Let $k$ denote the number of people in the group. We prove it by induction on $k$. If $k=1$ then the result obviously holds. Assume the result holds for any group with $k$ people, and take a group with $k+1$ people, $(p_1,\ldots,p_{k},p_{k+1})$, in which at least one has blue eyes, say $p_1$. Looking at the first $k$, $(p_1,\ldots,p_k)$, we can use the induction hypothesis to conclude that $p_1,p_2,\ldots,p_k$ each have blue eyes. Then looking at the last $k$, $(p_2,\ldots,p_k,p_{k+1})$, since at least one has blue eyes (say $p_k$), then they all have blue eyes by the induction hypothesis. In particular, $p_{k+1}$ has blue eyes. Therefore, they al have blue eyes, QED.
The reason this is incomplete is that the inductive step only works if $k\geq 3$, so that a proof would require the special case of showing that $1\in S$ implies $2\in S$ (the general argument we have does not cover that particular implication). That's where it all breaks down, of course. But the point is that sometimes ordinary induction also requires "special cases", though this tends to happen less often than with strong induction.
The step where you use the inductive hypothesis in the proof above is in the second line of the long display, where you are using that the inequality you want holds for both $a_{k-1}$ and for $a_{k-2}$. This requires you to assume that it holds for two numbers strictly smaller than $k$ (you don't need the fact that it holds for all numbers less than $k$ here, but you do end up needing it for more than just the immediately previous one).
In regular induction, your only assumption is that the result holds for the immediately previous number (for $k-1$, when you are trying to prove it for $k$; or for $k$, when you are trying to prove it for $k+1$). You make no assumptions about what happens for $\ell$ with $\ell\lt k-1$. In strong induction, you assume that it holds for all $\ell\lt k$, not just for $k-1$. Here, because you need the assumption for two smaller values of $k$, this argument would not work if you were only assuming that $a_{k-1}\lt\left(\frac{7}{4}\right)^{k-1}$ but were making no assumptions about $a_{k-2}$. There are ways to prove the result using ordinary induction, but this particular argument would not work.
Notice that since your proof requires you to have at least two smaller values than $k$, the argument will not work for either $k=1$ or $k=2$ (the first has no smaller values, the second has only one); that is why you end up having to prove the two special cases of $a_1$ and $a_2$. Again, this is not a "basis for the induction", but rather special cases of the inductive argument.