3
$\begingroup$

enter image description here

I don't understand why the author says that the inductive formula does not apply until $u_3$. The formula does not depend on other terms in the Fibonacci sequence, so I thought I could just prove it using weak proof of induction with base case $n=1$ only.

$\endgroup$

1 Answer 1

8
$\begingroup$

The Fibonacci sequence is defined to be $u_1=1$, $u_2=1$, and $u_n=u_{n-1}+u_{n-2}$ for $n\ge 3$. Note that $u_2=1$ is a definition, and we may have just as well set $u_2=\pi$ or any other number. Since $u_2$ shares no relation to $u_1$ (without considering any other $u_k$), we can't use induction to go from the case $n=1$ to $n=2$.

If we attempted it anyway, it would go something like this:

Base case $n=1$: (proved in the question statement)

Inductive step $(k)\rightarrow (k+1)$: Assume $u_k=\frac{\alpha^k-\beta^k}{\sqrt{5}}$. Then we have the formula $u_{k+1}=u_k+u_{k-1}$. How can we apply this? We only have information about $u_k$, but we also need information about $u_{k-1}$ to get information about $u_{k+1}$. Okay, so weak induction doesn't quite do it for us. Let's be lax and allow ourselves at this point to switch to strong induction so we can also assume that $u_{k-1}=\frac{\alpha^{k-1}-\beta^{k-1}}{\sqrt{5}}$. Brilliant! Now we can just do some plugging in and fiddling and get $$u_{k+1}=u_k+u_{k-1}=\frac{\alpha^{k}-\beta^{k}}{\sqrt{5}}+\frac{\alpha^{k-1}-\beta^{k-1}}{\sqrt{5}}=\frac{\alpha^{k+1}-\beta^{k+1}}{\sqrt{5}},$$ where the second equality comes from the formulas $\beta^2=\beta+1$ and $\alpha^2=\alpha+1$. This gives us exactly what we wanted, right?

Unfortunately, the answer is no. There is a huge gaping flaw with this proof, and that is that it doesn't work for $n=2$, so it doesn't work for any $n\ge2$ either.

Here's the issue: When we did our inductive step, we used the recurrence formula $u_{k+1}=u_k+u_{k-1}$, but this formula $\textit{isn't true}$ for $k+1=2$. In this case we have $u_2=u_1+u_0$, but we haven't defined $u_0$! In our world, $u_0$ $\textit{doesn't even exist}$.

Since the formula $u_{n}=u_{n-1}+u_{n-2}$ is only valid for $n\geq 3$, we must prove the $n=2$ case separately as part of our base cases, and once we have done that, the above proof will be correct.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .