0

I have this Fibonacci sequence

$F_i=i, i \in\{0,1\}, F_n=F_{n-1}+F_{n-2}, n \geq 2$

and have to prove by induction that:

$\forall n \geq 1, F_n \varphi+F_{n-1}=\varphi^n: \varphi \equiv \frac{1+\sqrt{5}}{2}$

and conclude $\varphi^{10}$

I've started the solution but I've not been able to finish :(

$\\ 1) ~ \text {prove for } n=1 \\ F_1=1, F_0=0 \\ F_1 \varphi+F_0=\varphi+0=\varphi=\varphi^1 \Rightarrow \mathrm{~OK } \\ ~ \\ 2) - \text {suppose that the equation is correct for } n \\ F_n \varphi+F_{n-1}=\varphi^n \\~\\ 3) ~ \text{prove for } n+1 \\ F_{n+1} \varphi+F_n=\varphi^{n+1} \\~\\ \text{ but from the question: } \\ F_n=F_{n-1}+F_{n-2} \\ \Rightarrow F_{n+1}=F_{n+1-1}+F_{n+1-2} \\ \Rightarrow F_{n+1}=F_n+F_{n-1} \\~ \\ F_{n+1} \varphi+F_n=\varphi^{n+1} \\ =\left(F_n+F_{n-1}\right) \varphi+F_n \\ =F_n \varphi+F_{n-1} \varphi+F_n \\ =F_n (\varphi+1) +F_{n-1}\varphi$

here I've stoped and not known how to complete help me please

engnajjar
  • 65

1 Answers1

2

You are very, very close. You've made a mistake in the last line: it should read $$F_n \varphi + F_{n-1} \varphi + F_n = F_n (\varphi + 1) + F_{n-1} \color{red}{\varphi}.$$ Then, you should observe that $$\varphi + 1 = \varphi^2,$$ because $\varphi$ is a root of the quadratic polynomial $$x^2 - x - 1 = 0.$$ Therefore, $$F_n (\varphi + 1) + F_{n-1} \varphi = F_n \varphi^2 + F_{n-1} \varphi = \varphi (F_n \varphi + F_{n-1}) = \varphi \varphi^n = \varphi^{n+1}.$$

heropup
  • 135,869
  • thank my friend and sorry for the mistake. $ F_n(\varphi+1)+F_{n-1} \varphi$ is found in my solution but it fell inadvertently :) can you please explain more about $\varphi+1=\varphi^2$ and $x^2-x-1=0$ – engnajjar Jun 09 '23 at 20:53
  • @engnajjar You could show that $\varphi + 1 = \varphi^2$ simply by computing $$\varphi + 1 = \frac{1 + \sqrt{5}}{2} + 1 = \frac{3 + \sqrt{5}}{2},$$ and $$\varphi^2 = \frac{(1+\sqrt{5})^2}{2^2} = \frac{6 + 2\sqrt{5}}{4} = \frac{3 + \sqrt{5}}{2},$$ or you can use the quadratic formula to solve $$x^2 - x - 1 = 0$$ to give $$x = \frac{1 \pm \sqrt{(-1)^2 - 4(1)(-1)}}{2(1)} = \frac{1 \pm \sqrt{5}}{2},$$ so $\varphi$ is one of the roots. This implies $$\varphi^2 - \varphi - 1 = 0,$$ or $$\varphi^2 = \varphi + 1.$$ – heropup Jun 09 '23 at 21:15
  • you are amazing thanks soooo much ^_^ – engnajjar Jun 09 '23 at 22:50