I am working through the beginning of Introduction to Algorithms, and came across the problem
Prove by induction that the $i$-th Fibonacci number satisfies the equality $$ F_{i} = \frac{\phi^{i} - \hat{\phi^{i}}}{\sqrt{5}}$$ where $\phi$ and $\hat{\phi}$ are the golden ratio and it's conjugate, respectively.
Now I know there are plenty of answers online regarding this proof, and I have already come to understand a few ways to approach it, but I am simply curious about the approach I originally took to solving the problem and whether it is valid or not.
I am fairly convinced it is invalid, but I want to double check and wonder if there is some mechanism in the proof I can change to validate it.
My approach:
First, I proved (trivially) that both $\phi$ and $\hat{\phi}$ satisfy the equation \begin{equation} x^{2} = x+1 \tag{1} \end{equation}
Then after trivially proving the base cases for the inductive proof, for the inductive step we assume $$ F_{k} = \frac{\phi^{k} - \hat{\phi^{k}}}{\sqrt{5}}$$ for some $k \in \mathbb{Z}^{+}$.
Then for $k+1$, we have \begin{align} \frac{\phi^{k+1} - \hat{\phi^{k+1}}}{\sqrt{5}} &= \frac{\phi^{k-1}\phi^{2} - \hat{\phi}^{k-1}\hat{\phi^{2}}}{\sqrt{5} } \\ &= \frac{\phi^{k-1}(\phi + 1) - \hat{\phi}^{k-1}(\hat{\phi} + 1)}{\sqrt{5}} && \text{by (1)} \\ &= \frac{\phi^{k} - \hat{\phi}^{k}}{\sqrt{5}} + \frac{\phi^{k-1} - \hat{\phi}^{k-1}}{\sqrt{5}} \\ &= F_{k} + F_{k-1} \\ &= F_{k+1} && \text{by definition} \end{align}
This looks downright incorrect to me because it implies that the inductive step holds for $k-1$, which is not permitted in inductive proofs, correct? If so, are there any measures I can take to validate this proof? I've already worked out a solution going the other way with the recurrence relation, I'm just curious how close this might be (I haven't touched inductive proofs in a while)
For $k\ge 1$, let $A_k$ be the assertion that $F_k$ and $F_{k-1}$ both satisfy the condition.
You have shown that if $A_k$ holds, then the condition is satisfied at $k+1$, and therefore that $A_{k+1}$ holds. So you have proved that $A_n$ holds for all $n$, and therefore that $F_n$ satisfies the condition for all $n$.
For another approach that is more generally useful, please see strong induction aka complete induction.