So I understand that induction leads from the fifth axiom of natural numbers, where we say that we show the statement must be true for P(n + 1) if it is true for P(n) for some arbitrary n, then for all P(n) (starting at our base case), it must be true for its successor.
But can we use P(n - 1) in our proof?
For example, assume that P(n) says that $F(n)^2 + F(n + 1)^2 = F(2n + 1)$, are we allowed to also assume P(n - 1), namely that $F(n - 1)^2 + F(n)^2 = F(2n)$?
This question arose because I looked at the proof here: here and it seemed like they assumed exactly that.
My question is: why is this logically valid?
Here $F(0)=0$, $F(1)=1$, etc.
If you assume $P(n)$, then you can't assume $P(n-1)$. But you can assume $P(i)$ holds for all $i\leqslant n$ and then prove $P(n+1)$. If you do that, you'd need to make sure you handle all appropriate base cases. The logic is as follows:
We prove it by contradiction. Assume there exists $m$ such that $P(m)$ is not true. Then let $n$ be the minimum $m\in\mathbb{N}$ for which $P(m)$ does not hold.
Case $1$: $n=0$. We know $F(0)=0$, $F(1)=1$, $F(2\cdot 0+1)=1$, and $0^2+1^2=1$, a contradiction. So $n=0$ is impossible, because $P(0)$ does hold.
Case $2$: $n=1$. We know $F(1)=1$, $F(2)=1$, and $F(2\cdot 1+1)=F(3)=2$. Then $1^2+1^2=2$, a contradiction. So $n=1$ is impossible, because $P(1)$ does hold.
Case $3$: $n>2$. In this case, $P(n-1)$ and $P(n-2)$ both hold, and you go as in the link.
That's the logic behind the linked argument, and the reason it refers to two base cases, $n=0$ and $n=1$.
In general, you can show that if $P(0)$ holds and $P(n)$ implies $P(n+1)$ for any $n$, then $P(n)$ holds for all $n$, This is called weak induction. But you can also argue that if $P(0)$ holds and if $P(k)$ holds for all $k\leqslant n$, then $P(n+1)$ also holds, then $P(n)$ holds for all $n$. This is called strong induction. In such a situation, if your inductive step to prove $P(n)$ involves $P(n-1)$, $\ldots$, and $P(n-k)$, then you will likely have to perform $k$ base cases.
Either way, the underlying logic is the same. If $A$ is the set of $n$ for which $P(n)$ fails, then either $A$ is empty ($P(n)$ holds for all $n$), or it has a minimum, $n$. But if we know that $P(0)$ holds, $n$ cannot be equal to zero. And if we know that $P(m)$ must be true whenever $P(i)$ is true for all $i<m$, then $P(n)$ must be true as well, by minimality, and we arrive at a contradiction.