recursive to standard convertion

Question

I have been trying to find an equation for a sequence, and got interested on how to convert any recursive sequence ex: $F_n=F_{n-1}+F_{n-2},\space F_0=1,\space F_1=1$ into a standard equation
ex: $F_n=\frac 1{\sqrt 5}(\frac {1+\sqrt 5}2)^{n+1}-\frac 1{\sqrt 5}(\frac {1-\sqrt 5}2)^{n+1}$ I decided to search around but only got beginners algebra stuff, in fact the only helpful thing I found was a video on how to do it with the Fibonacci sequence which doesn't help me with the equation I have. if anyone could give me a link to something helpful, that would be appreciated, and if you want to tackle the equation, here you go:
$f_n=\begin{cases} \text{if n is even} & f_{\big(\frac n2\big)}+f_{\big(\frac n2-1\big)}\\ \text{if n is odd} & f_{\big(\frac{n-1}2+1\big)} \\ \end{cases}\space f_0=1,\space f_1=1$
or $$f_n=\frac{(-1)^n+1}2\bigg(f_{\big(\frac n2\big)}+f_{\big(\frac n2-1\big)}\bigg)-\frac{(-1)^{n}-1}2\bigg(f_{\big(\frac{n-1}2+1\big)}\bigg),\space f_0=1,\space f_1=1$$ if you get an answer can you show how you got it and what it is?

Answer 1

We can make the following.

We'll choose values $k$ and $m$, for which our sequence it's $$F_n+kF_{n-1}=m\left(F_{n-1}+kF_{n-2}\right)$$ or $$F_n=(m-k)F_{n-1}+mkF_{n-2}.$$ Thus, $$m-k=1$$ and $$mk=1,$$ which after solving of this system gives $$k=\frac{\sqrt5-1}{2}$$ and $$m=\frac{1+\sqrt5}{2}.$$ Id est, $$F_n+\frac{\sqrt5-1}{2}F_{n-1}=\frac{1+\sqrt5}{2}\left(F_{n-1}+\frac{\sqrt5-1}{2}F_{n-2}\right).$$ We see that $a_n=F_n+\frac{\sqrt5-1}{2}F_{n-1}$ is a geometric progression, $a_1=1$ and we obtain: $$F_n+\frac{\sqrt5-1}{2}F_{n-1}=a_n=a_1\left(\frac{1+\sqrt5}{2}\right)^{n-1}=\left(\frac{1+\sqrt5}{2}\right)^{n-1}.$$

Now, use the telescopic sum.

Can you end it now?

Answer 2

Your original equation is equivalent to (for integers k):

$$f_{2k} = f_{k} + f_{k-1} $$ $$f_{2k-1} = f_{k}$$ Or, using matricies: $$ \begin{pmatrix} f_{2k}\\ f_{2k-1}\\ \end{pmatrix} = A \begin{pmatrix} f_{k}\\ f_{k-1}\\ \end{pmatrix} ,\qquad A= \begin{pmatrix} 1 & 1\\ 1 & 0\\ \end{pmatrix} $$ By recursively applying this to an integer of the form $2k=2^r$: $$ \begin{pmatrix} f_{2^r}\\ f_{(2^r-1)}\\ \end{pmatrix} = A^r \begin{pmatrix} f_{1}\\ f_{0}\\ \end{pmatrix} ,\qquad A^r= \begin{pmatrix} {F}_{r+1} & {F}_{r}\\ {F}_{r} & {F}_{r-1}\\ \end{pmatrix} $$ where ${F}_{r}$ is the rth Fibonacci number, ${F}_{0} = 0$

resolving components and using initial conditions: $$ f_{2^r} = {F}_{r+1} + {F}_{r} = {F}_{r+2} $$ similairly, $$ f_{(2^r-1)} = {F}_{r+1} $$ I couldn't take it any further than this for other values of k... I got the idea to use matrices from this German guy on YouTube (link is him doing a similar method but with the Fibonacci sequence itself): https://www.youtube.com/watch?v=WT_TGxQrV1k