What is the second principle of finite induction?

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)

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.

That's not a very good example. This principle usually goes by the name of strong induction, and the point is that while it's equivalent to ordinary induction, it's often more convenient to use in proofs. For proving a sequence $P(k)$ of identities, it's often straightforward to write $P(k+1)$ in terms of $P(k)$, but for a more complicated sequence of statements one might need the stronger assumption that $P(1), ... P(k)$ all hold in order to readily deduce $P(k+1)$.

For example, if one is proving a sequence of statements $P(k)$ about finite graphs with $k$ vertices, one general proof strategy is to break a graph up into two smaller graphs, and if the statement for each of the smaller graphs implies the statement for the larger graph, we are done by strong induction, but not necessarily by weak induction, since the smaller graphs do not necessarily have sizes $1$ and $k-1$.

As another example, here's a nice exercise. Consider the sequence $a_n$ with $a_1 = 1$ and

$$a_{2n} = a_n$$ $$a_{2n+1} = a_n + 1.$$

Try proving by strong induction that $a_n$ is the sum of the digits of $n$ in base $2$. Can you see why this proof is difficult to phrase using weak induction?

There is a common misconception that strong induction is somehow "stronger" than normal induction, but it isn't really. Strong induction is just the special case of normal induction in which the induction hypothesis $P(n)$ takes the form "for all $m < n$, $Q(m)$". Thus strong induction is actually a limited form of the principle of induction, because not all induction hypotheses are of that special form. On the other hand, any proof by strong induction can be trivially rephrased as a proof by "weak" induction.

One reason for the terminological difficulty is that the only place that people talk about "strong induction" is in introductory courses. There, "use strong induction" can be a hint about what sort of induction hypothesis to choose. In these classes, the principle of induction is stated somewhat informally, so it may not be obvious what counts as a legal induction hypothesis in the first place.

In contexts where the principle of induction is stated formally, e.g. Peano arithmetic, nobody talks about strong induction at all. The axiom scheme for induction in Peano arithmetic simply includes all axioms of the form $$ (P(0) \land (\forall n)(P(n) \to P(n+1)) \to (\forall n)(P(n)) $$ where $P$ is any formula of Peano arithmetic. This includes formulas of the form $(m < n)\to Q(m)$ as well as all other formulas.

The second principle of induction to which you refer is sometimes called the strong principle of induction, as opposed to the usual one which is also sometimes called the weak principle of induction. This distinction is only apparent at first since they are both equivalent, so there's no harm in using the strong version of it and thinking you're using something much more powerful.

As you can see in this post, the difference is basically that in the weak principle of induction, your inductive hypothesis is just that the property you want to prove is true for some integer $n$, and then you show that it also holds for $n+1$.

But in the strong version you assume that the property holds for all integers up to $n$, that is, you assume it holds for $0, 1, 2, \dots , n$.

An example of a theorem that is sometimes proved using the strong version is the so called Fundamental Theorem of Arithmetic. The theorem basically consists of two parts, one is showing the existence of a factorization into primes and the other is showing that "the" factorization is unique. So for instance if you're showing that a factorization exists by induction, then in the inductive step you'll have to prove that if $n$ can be factored as a product of primes, the so can $n+1$.

The problem now is that you have basically two options, that $n+1$ is a prime in which case you're done, or that $n+1$ is composite, thus it can be factored as $n+1 = ab$ where $1 < a \leq n$ and $1 < b \leq n$. Now you can see where the strong principle comes in handy because if you assume not only that $n$ can be factored as a product of primes, but also that all the integers greater than $1$ can (up to $n$ of course), then you immediately know that both $a$ and $b$ are products of primes, say $a = p_1 \cdots p_k$ and $b = q_1 \cdots q_s$ with $p_i$ and $q_j$ primes, then $n+1 = ab = p_1 \cdots p_k \cdot q_1 \cdots q_s$ is also a product of primes, so the induction is complete.