2
$\begingroup$

I have $f_{n}=f_{n-1}+f_{n-2}; f_{n}= [0,1,1,2,3,5,8,13,21,34,55,89,144,233,...]$ for which I note that indeed, 2 divides 4, and $f_{2}$ divides $f_{4}$.

I am wondering if a proof by induction is sufficient, and exactly how would I go about doing that in this case? Or could I use the closed form formula to prove it: $\dfrac {1} {\sqrt {5}} [( \dfrac {1+\sqrt {5}} {2}) ^{n}-( \dfrac {1-\sqrt {5}} {2}) ^{n}]$

Thanks!

$\endgroup$
2
$\begingroup$

Hint: Use $\dfrac{A^{pq}-B^{pq}}{\sqrt{5}} = \dfrac{(A^p-B^p)}{\sqrt{5}}(A^{p(q-1)}+ A^{p(q-2)}B^p+\cdots + B^{p(q-1)})$. Thus you need to show the second factor is an integer. But you can rewrite it as the sum of the terms $\pm (A^k + B^k)$, and you have to show each $A^k+B^k$ is an integer. And this can be done by induction and is easier than the original one.

$\endgroup$
1
$\begingroup$

you can also use following identity $$f_{kn+c}=\sum_{i=0}^k \dfrac{k!} {i!(k-i)!} \cdot f_{c-i} \cdot f_{n}^i \cdot f_{n+1}^{k-i}$$ which can be easily proved using induction.Plugging in $$c=n$$ your problem becomes trivial

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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