From SICP:
Exercise 1.13: Prove that $\operatorname{fib}(n)$ is the closest integer to $$\frac{\phi^{n}}{\sqrt{5}}, \text{ where } \phi=\frac{1+\sqrt{5}}2.$$ Hint: Let $$\varphi=\frac{1-\sqrt{5}}2.$$ Use induction and the definition of the Fibonacci numbers (see 1.2.2) to prove that $$\operatorname{fib}(n)=\frac{\phi^{n}-\varphi^{n}}{\sqrt{5}}.$$
My background:
- Some programming experience, including recursion
- Some algebra
- very basic recursive sequence (just explored)
- Very basics of induction (just explored)
I thought I'd take a stab at this exercise. I am aware I may not be able to do this because it might require some mathematical tools I am not yet able to use, but I just want to try it and see what happens.
Let $p1(n)$ be the proposition that $$\operatorname{fib}(n)=\frac{\phi^{n}-\varphi^{n}}{\sqrt{5}}$$
Base case: $p_1(0)$ is true. $$\operatorname{fib}(0)=\frac{\phi^{0}-\varphi^{0}}{\sqrt{5}}=0$$
Inductive hypothesis: assume $p_1(n)$ is true. $$\operatorname{fib}(n)=\frac{\phi^{n}-\varphi^{n}}{\sqrt{5}}$$
Inductive step: $p_1(n)$ is true $ \implies p_1(n+1)$ is true $$\operatorname{fib}(n+1)=\frac{\phi^{n+1}-\varphi^{n+1}}{\sqrt{5}}$$
Solution: we can rewrite the left side as: $$\operatorname{fib}(n)+\operatorname{fib}(n-1)=\frac{\phi^{(n+1)}-\varphi^{(n+1)}}{\sqrt{5}}$$
Since I know that $$\operatorname{fib}(n)=\frac{\phi^{n}-\varphi^{n}}{\sqrt{5}}$$ I can substitute.
$$\frac{(\phi^{n}-\varphi^{n})}{\sqrt{5}}+((\phi^{(n-1)}-\varphi^{(n-1)})/\sqrt{5})=(\phi^{(n+1)}-\varphi^{(n+1)})/\sqrt{5}$$
Now I have to combine the terms. I have to make sure of two things: $$\phi^{n}+\phi^{(n-1)}=\phi^{(n+1)}$$ and $$\varphi^{n}+\varphi^{(n-1)}=\varphi^{(n+1)}$$
It is stated in the book that: $fi^2=fi+1$ When I used this equation, I got the following transformations.
- $$\phi^{1}=\phi$$
- $$\phi^{2}=(\phi+1)$$
- $$\phi^{3}=(2\phi+1)$$
- $$\phi^{4}=(3\phi+2)$$
- $$\phi^{5}=(5\phi+3)$$
Much like how the fibonacci numbers are iteratively generated. More generally, I would say that: $$\phi^{n}=\operatorname{fib}(n)\phi+\operatorname{fib}(n-1)$$ This is just a guess, I will assume it for now. I will try to prove this at the end.
$\varphi$ is the same. For some reason the equation. $\varphi^{2}=\varphi+1$ also appears to hold. I would assume $\varphi^{n}$ is the same as with $\phi^{n}$.
So, back to $p_1$
Using my transformations of $\phi^{n}$ above: $$\phi^{(n+1)}=\operatorname{fib}(n+1)\phi+\operatorname{fib}(n)$$
I can finally confirm that:
$$\phi^{n}+\phi^{(n-1)}=(\operatorname{fib}(n)\phi+\operatorname{fib}(n-1))+(\operatorname{fib}(n-1)\phi+\operatorname{fib}(n-2))$$ using the definition of $\operatorname{fib}$: $$\operatorname{fib}(n)\phi+\operatorname{fib}(n-1)\phi=\operatorname{fib}(n+1)\phi$$ $$\operatorname{fib}(n-1)+\operatorname{fib}(n-2)=\operatorname{fib}(n)$$ add all = $$\operatorname{fib}(n+1)\phi+\operatorname{fib}(n)=\phi^{(n+1)}$$
I believe since $\varphi$ and $\phi$ appear to have the same transformations, I think I already proved $$\varphi^{n}+\varphi^{(n-1)}=\varphi^{(n+1)}$$
So, I believe $p_1(n+1)$ is true and I believe I have proven $p_1$.
Now, on to the original exercise: $\operatorname{fib}(n)$ is the closest integer to $\phi^{n}/\sqrt{5}$$ because $$\operatorname{fib}(n)-\varphi^{n}/\sqrt{5}=\phi^{n}/\sqrt{5}$$. Is this correct?
Now, I would like to prove $\phi^{n}$ because I have just guessed it earlier.
Let $p_2(n)$ be the proposition that $$\phi^{n}=\operatorname{fib}(n)\phi+\operatorname{fib}(n-1)$$ for all positive integers $>0$
base case: $p_2(1)$ is true. $$\phi^{1}=\phi+0=\phi$$
Inductive hypothesis: assume $$\phi^{n}=\operatorname{fib}(n)\phi+\operatorname{fib}(n-1)$$ for all positive integers $>0$
Inductive step: $p_2(n)$ implies $p_2(n+1)$ is true $$\phi^{(n+1)}=\operatorname{fib}(n+1)\phi+\operatorname{fib}(n)$$ for all positive integers $> 0$
Solution: $$\phi^{(n+1)}=\phi\cdot \phi^{n}$$ so: $$\phi^{(n+1)}=(\operatorname{fib}(n)\phi+\operatorname{fib}(n-1))\phi$$ Since $\operatorname{fib}(n)$ is the closest integer to $\phi^{n}/\sqrt{5}$, we can substitute this: $$\phi^{(n+1)}=((\phi^{n}/\sqrt{5})\phi+(\phi^{(n-1)}/\sqrt{5}))fi$$ $$((\phi^{n}/\sqrt{5})\phi)\phi=(\phi^{(n+1)}/\sqrt{5})\phi=\operatorname{fib}(n+1)\phi$$ $$(\phi^{(n-1)}/\sqrt{5})\phi=\phi^{(n)}/\sqrt{5}=\operatorname{fib}(n)$$ add all $$\operatorname{fib}(n+1)\phi+\operatorname{fib}(n)$$ That I think is the solution.
Now, I don't really know if what I did is correct. I just assume some things (e.g. $\phi^{2}=\phi+1$) but I don't really know why that is true. One thing that bothers me so much is: In order to prove that $\operatorname{fib}(n)$ is the closest integer to $$\phi^{n}/\sqrt{5}$$, I first have to prove $p_1$. In order to make sure that $\phi^{n}$ generates like fibonacci numbers on $p_1$, I proved $p_2$. But $p_2$ also requires me to assume that $\operatorname{fib}(n)$ is the closest integer to $$\frac{\phi^{n}}{\sqrt{5}}!$$ I feel like I am doing something very wrong here.
Did I do something right? Or I have no idea what I'm really doing?