I'm going to try and explain the subtlety you've noticed from a different angle. For reference, I'm reprinting your argument here, naming the proposition $P(n) : F_n = \phi^n+(1-\phi)^n$.
Let $n = 1$. Then $F_n = 1$ and $\phi + 1 - \phi = 1$. Thus, the proposition $P(1)$ holds, establishing our base case.
So far, so good.
Assume that $P(k)$ holds for all natural numbers $k\leq n$. Then $F_{n+1} = F_n + F_{n-1} = \phi^n + (1-\phi)^n + \phi^{n-1} + (1-\phi)^{n-1} = \phi^{n-1}(1 + \phi) + (1-\phi)^{n-1}(2-\phi) = \phi^{n-1}\phi^2 + (1 - \phi)^{n-1}(1-\phi)^2 = \phi^{n+1} + (1-\phi)^{n+1}$. Thus $P(n+1)$ holds. By mathematical induction, we have $P(n)$ for all $n \in N$.
This uses $P(n)$ and $P(n-1)$, which on the surface looks good - but note that this requires both $P(n)$ and $P(n-1)$ explicitly. The false statement that you're relying on is the statement '$(\forall k\leq n P(k)) \implies (P(n) \wedge P(n-1))$', because this statement is ill-defined when $n=1$ (assuming that the 'base case' is $n=1$, of course, and thus $P(0)$ is technically undefined.) This means that you haven't actually shown $\forall n \bigl(\left(\forall k\leq n P(k)\right)\implies P(n+1)\bigr)$, which is what you need for your induction to work.
This should explain why virtually all Fibonacci proofs need two 'base cases' : because generally they use the induction principle $P(n-1)\wedge P(n)\implies P(n+1)$, they need both $n=1$ and $n=2$ 'base cases' to get around the issue with the definition of $P(0)$ (or alternately, $n=0$ and $n=1$ base cases).