# recursive to standard convertion

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?

• I'm confused... this is the Fibonacci sequence, right? It's shifted a little (the $0$th and $1$st terms are $1$ instead of the $1$st and $2$nd terms), but it generates the same numbers. Can't you just adapt the formula for the $n$th Fibonacci number? – Theo Bendit Jun 5 at 4:40
• @TheoBendit are you talking about the examples I gave? – spydragon Jun 5 at 4:41
• Right, that's what I missed: they are examples, not what you're interested in. There are plenty of resources on the web for how to solve homogeneous second order linear recurrence relations, e.g. math.berkeley.edu/~arash/55/8_2.pdf – Theo Bendit Jun 5 at 4:46
• Mind you, that won't help your given recurrence relation. I don't think you'll find any general methods to tackle such a monster. – Theo Bendit Jun 5 at 4:49
• @TheoBendit thank you, is that what there called. no wonder I couldn't find anything about them. and even though it might not help I'll see anyway – spydragon Jun 5 at 4:50

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?

• Can the down-voter explain your step? – Michael Rozenberg Jun 5 at 7:05
• (I am not the one who down voted) I assume its because that your solution is for the Fibonacci sequence and not for what I'm looking for – spydragon Jun 7 at 16:43
• @spydragon I explained how you can get this formula. It's exactly, that you are looking for. By the way, this method works for any recurrence in the type $a_{n+2}=pa_{n+1}+qa_n$ or $a_{n+k}=p_1a_{n+k-1}+...+p_ka_n.$ – Michael Rozenberg Jun 7 at 17:04
• maybe so but my equation isn't that it isn't just plain addition or subtraction it has to do with multiplication as well which can't be written the way that you have put it (I think) and even if it can, you would probably have to explain it more in depth (read my bio to know why). – spydragon Jun 7 at 20:17
• @spydragon I am ready to explain more. You need to say only, that you want this. Which step in my solution is not clear? – Michael Rozenberg Jun 7 at 20:50

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

• sorry, this is incorrect. only because of a mistake that I made $f_2$ is actually supposed to be $f_0+f_1$ which equals $2$ – spydragon Jun 5 at 14:20
• edited that part out :) – S. Dauncey Jun 6 at 6:21
• thank you for your help. – spydragon Jun 6 at 14:11
• your second equation $f_{2k-1}=f_k$ should be $f_{2k+1}=f_k$, sorry I didn't notice this earlier. try to generate this sequence with you'r equations to check it: $1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3,...$ with the first two terms being $f_0$ and $f_1$ – spydragon Jun 7 at 14:29
• may I ask, how did the Fibonacci numbers appear? and shouldn't $F_{r+1}$ be $F_{r+2}$? – spydragon Jun 14 at 14:22