Why does this fibonacci sequence proof require P(n + 1) for n = 1 be defined explicitly? I am going through Donald Knuth's The Art of Computer Programming, Vol 1, Chapter 1.2.1: Mathematical Induction.
Knuth's inductive strategy (to prove a statement $P(n)$ is true for all positive integers $n$) is:
a.  Give a proof that $P(1)$ is true. 
b. Give a proof that "if all of $P(1), P(2), \cdots, P(n)$ is true, then $P(n + 1)$ is also true". He notes that this proof should be valid for any positive integer $n$.
As an example, he presents a proof related to the Fibonacci numbers, namely that if:
$F_0 = 0$ 
$F_1 = 1$ 
$F_n = F_{n - 1} + F_{n - 2}$
and that:
$\phi = \frac{1 + \sqrt{5}}{2}$
then we can prove
$F_n \leq \phi^{n - 1}$
inductively.
The way Knuth does this is as follows:

For step (a): If $n = 1$: $F_1 = 1 = \phi^{0} = 1$, so we have proved the base case.

Then, in order to tackle step (b), he writes:

First notice that P(2) is also true, since $F_2 = 1 < 1.6 < \phi^{1} = \phi^{2 - 1}$. Now if all of P(1) through P(n) are true, we know that P(n - 1) and P(n) are true; that is:

$F_{n - 1} \leq \phi^{n - 2}$
and
$F_{n} \leq \phi^{n - 1}$.
He uses this to prove the relationship holds for $F_{n + 1}$, using a fact about $\phi$ and through substitution of the prior inequalities, which I understand.
My problem is that at the end of the proof, Knuth writes:

Notice that we approached step (b) [the step of proving that if it holds for P(n), it holds for P(n + 1)] in two different ways here. We proved P(n + 1) directly when n = 1, and we used an inductive method when n > 1. This was necessary, since when n = 1 our reference to P(n - 1) = P(0) would not have been legitimate.

What does he mean by this last line? The only thing I can garner is that he means the general relationship of
$F_{n+1} = F_{n} + F_{n - 1} \leq \phi^{n - 2} + \phi^{n - 1} = \phi^{n}$
does not hold if you used it to show the inequality holding at $n = 1$, because then you would get:
$F_{1} = F_{0} + F_{-1} \cdots$, where a -1 makes no sense.
But I don't know if I'm misunderstanding him, because I would think that if n = 1, and you were trying to prove $P(n + 1) = P(2)$, then you could easily show:
$F_{2} = F_{1} + F_{0} \leq \phi^{0} + \phi^{-1} \cdots $, because $F_0 = 0 \leq \frac{1}{\phi}$.
Is there something I'm just not understanding? Sorry if I didn't explain my problem right. I've used induction in the past but my math has always been shaky so I wanted to relearn it.
The only other thing I can proffer is that I believe in order for us to use the $F_{n - 1} \leq \phi^{n - 2}$ and other inequalities, you have to use strong induction, because regular induction only allows you to use P(n) in proving P(n + 1), but in proofs with recurrence relations, you frequently have to use P(n - 1, etc...) to get your proof right. But I may also be misunderstanding strong induction vs. regular induction.
Thanks for your help! If this is off-topic or a duplicate, I'd greatly appreciate a pointer in the right direction to the prior post that clears this up.
 A: Thanks to both Anne Bauval and Klaus for their comments. I'm collecting their answers here.
Essentially, it seems that Knuth may have made an error in the book, namely, that he forgot P(0) was in fact defined and therefore legitimate.
The proof, as far as I can tell, is follows (a quick sketch):

*

*Prove P(0), P(1) holds.

*One can note that because $F_{n} = F_{n - 1} + F_{n - 2}$, it may be possible to create a formula for the inequality being proved using this recursive definition, that is, that: $F_{n} = F_{n - 1} + F_{n - 2} \leq \phi^{(n - 1) - 1} + \phi^{(n - 2) - 1} \leq \phi^{n - 1}$. One should prove P(2) with this, either directly (as Knuth did), or with this new inequality.

*Then, the inductive assumption is that both the general inequality and the new inequality that we wrote hold for P(2) all the way through P(n).

*With this inductive assumption, you can now prove P(n + 1). The way to do this is to use the new inequality to express $F_{n + 1}$, so you need to use: $F_{n + 1} = F_{n} + F_{n - 1} \cdots$ along with the facts you already know (and the fact that $1 + \phi = \phi^{2}$) to show this holds for P(n + 1).

Thanks for your help! I will see what Professor Knuth has to say about this, if any.
If there are any problems or errors I've made in my proof, please make a comment and I will try to edit it.
A: I don't think he's made a mistake, but rather he's trying to illustrate a point about the general template of the proof and why we need multiple base cases. His choice of example and wording seem to have confused you a bit. It seems to me like his point might be as follows:
As you say, there is a template to prove a statement $P(n)$ for all positive integers $n$, where we

*

*Prove $P(1)$.

*Prove that $P(1), \dotsc, P(n)$ together imply $P(n + 1)$ for all positive integers $n$.

The situation with this Fibonacci numbers proof is as follows: we have a statement $P(n)$ that is (or can be) defined for non-negative integers. We want to prove that $P(n)$ holds for all positive integers (it doesn't matter if it holds for non-negative integers, the point of the example is we're proving it for positive integers, since that is what "proof by induction" does for us). We do this using the following template:

*

*Prove $P(1)$.

*Prove $P(2)$.

*Prove that $P(n), P(n - 1)$ together imply $P(n + 1)$ for all positive integers $n$.

This template is always valid, which we can prove using the first template. Crucially, when we're proving this, we have to handle the case $n = 1$ separately in the induction step, using the fact that we proved $P(2)$. Then for $n > 1$, we use 3. (so in fact part 3. of this template might as well assume $n > 1$, but this doesn't change the strength of the template).
I believe his point is that if you omit the "Prove $P(2)$" step, the second template is no longer valid in general (even though $P(n - 1)$ is always defined, so you can "legitimately" refer to it in some sense). You may find it illuminating to think of a statement $P(n)$ defined for non-negative integers, which satisfies 1. and 3. of the second template but nevertheless does not hold for all positive $n$. Even though in this case $P(0)$ is true, the reason the reference to $P(0)$ is "illegitimate" is that we haven't proved it, and it might not be true in general.
Indeed an alternative template proves $P(0)$ instead of $P(2)$. But that doesn't mean he's wrong to say it would be invalid to omit the proof of $P(2)$. (and this alternative template is in a sense weaker than the one above! There are statements $P(n)$ that hold for all positive $n$ but not $0$. The alternative works exactly for statements that hold for all non-negative $n$).
This issue is fairly subtle and depends on how formal you're being about what "proof by induction" means, and what your statement of it is exactly. In practice, once you become used to it this isn't really something to worry about. You should become fairly fluent in what starting points you can take and how many base cases you should use for what. There are many such valid templates, and some of them don't even have a base case at all! The takeaway is that if you wish to refer to two previous cases in the induction step, you will usually have to prove two base cases.
