Induction proof error

I saw this problem in a book (not homework),

Assuming $L(n) = F(n)$ for$ n = 1,2,\cdots, k$ where $L(n)$ is Lucas Number and $F(n)$ is Fibonacci number.

$$\qquad L(k+1) = L(k) + L(k-1) \qquad \tag{by definiton}$$

$$ \qquad\qquad= F(k) + F(k-1) \tag{assumption}$$

$$ \ =F(k+1)$$

Hence, by principle of Mathematical induction, $F(n) = L(n)$ for each positive number $n$.

Is the reason why the proof is incorrect is because you can't assume that $L(n) = F(n)$ because that is not the relationship / definition of Lucas numbers in terms of Fibonacci numbers.

Solution 1:

Your induction step is well-defined only for $\,k\ge 2\,$ since for $\,k\le 1\,$ the term $\,L(k-1)\,$ is not defined. The recurrence lifts equality at the prior two indices to the current index. It cannot be used to deduce equality at the initial indices $\,n = 1,2$ (the "initial conditions" = base cases).

Generally, two solutions of the recurrence are equal iff they have equal $\rm\color{#c00}{initial\ conditions}$. Below is a proof of the uniqueness theorem for second order recurrences

Theorem $\ $ If $\,f',f\,$ are both solutions of the recurrence $\,f_{n+2} = a f_{n+1} + b f_n\,$ for all $\,n\ge 0\,$ then $\,f_n = f'_n\,$ for all $\,n\ge 0\iff \color{#c00}{f'_0 = f_0}\,$ and $\,\color{#c00}{f'_1 = f_1}$

Proof $\ (\Rightarrow)\ $ Clear. $\ (\Leftarrow)\ $ $\,f'_n = f_n\,$ for $\,n = 0,1\,$ by hypothesis. If $\,n\ge 2\,$ then suppose for induction they are equal at all indices $< n.\,$ Applying the recurrence and induction we have

$$\begin{align} f'_n\ =&\ \ a\ f'_{n-1}\! + b\, f'_{n-2}\\ =&\ \ a\,f_{n-1}\! + b\, f_{n-2}\ \ \text{ by induction hypothesis}\\ =&\ \ f_n\end{align}$$

Remark $\ $ The recurrence enables us to inductively lift the equality of the sequences at any two consecutive integer indices (initial conditions) to equality at all larger indices. The initial conditions provide the basis (foundation) of the lifting. Exactly the same proof works for a $k\,$th order recurrences, except you need equality at $\,k\,$ consecutive integers to serve as the base of the induction.

Solution 2:

We have to prove $F(1)=L(1)$ and $F(2)=L(2)$, which is false. That is the reason why the proof is incorrect.

Solution 3:

This looks corny after someone already pointed this out, but you have to establish the assumption is true for some set of points. Now you can't just show $L(1)=F(1)$ because you need $L(k)$ and $L(k-1)$ to build on. Thus you would have to show it to be true for two consecutive values of $L$