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.

up vote 5 down vote accepted

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.