# Closed form solution of Fibonacci-like sequence

Could someone please tell me the closed form solution of the equation below.

$$F(n) = 2F(n-1) + 2F(n-2)$$

$$F(1) = 1$$ $$F(2) = 3$$

Is there any way it can be easily deduced if the closed form solution of Fibonacci is known?

-
The same solution method should work.... – Hurkyl Jul 7 '12 at 19:11
Well, how would you derive the Binet formula for Fibonacci numbers in the first place? You can adapt the same technique to this case. – J. M. is back. Jul 7 '12 at 19:15
I think we should know two "base cases," e.g. $$F(0)=1\\F(1)=1$$ otherwise we can never get the numerical value of $F(n)$. – Argon Jul 7 '12 at 19:17
@Argon, of course, but in the absence of base cases, we could still have a formula with two arbitrary constants... – J. M. is back. Jul 7 '12 at 19:23
For your particular initial conditions, you should be getting $$\frac1{12}\left((3-\sqrt{3})\left(1-\sqrt{3}\right)^k+(3+\sqrt{3})(1+\sqrt 3)^k\right)$$ – J. M. is back. Jul 7 '12 at 19:43

Any of the standard methods for solving such recurrences will work. In particular, whatever method you would use to get the Binet formula for the Fibonacci numbers will work here, once you establish initial conditions. If you set $F(0)=0$ and $F(1)=1$, as with the Fibonacci numbers, the closed form is

$$F(n)=\frac{(1+\sqrt3)^n-(1-\sqrt3)^n}{2\sqrt3}\;;$$

I don’t see any way to derive this directly from the corresponding closed form for the Fibonacci numbers, however.

By the way, with those initial values the sequence is OEIS A002605.

Added: The general solution is $$F(n)=A(1+\sqrt3)^n+B(1-\sqrt3)^n\;;\tag{1}$$ Argon’s answer already shows you one of the standard methods of obtaining this. To find $A$ and $B$ for a given set of initial conditions, just substitute the known values of $n$ in $(1)$. If you want $F(1)=1$, you must have $$1=F(1)=A(1+\sqrt3)^1+B(1-\sqrt3)^1\;,$$ or $A+B+\sqrt3(A-B)=1$. To get $F(2)=3$, you must have \begin{align*}3&=F(2)=A(1+\sqrt3)^2+B(1-\sqrt3)^2\\ &=A(4+2\sqrt3)+B(4-2\sqrt3)\;, \end{align*}

or $4(A+B)+2\sqrt3(A-B)=3$. You now have the system

\left\{\begin{align*}&A+B+\sqrt3(A-B)=1\\ &4(A+B)+2\sqrt3(A-B)=3\;. \end{align*}\right.

Multiply the first equation by $2$ and subtract from the second to get $2(A+B)=1$, and multiply the first equation by $4$ and subtract the second from it to get $2\sqrt3(A-B)=1$. Then you have the simple system \left\{\begin{align*}&A+B=\frac12\\&A-B=\frac1{2\sqrt3}\;,\end{align*}\right. which you should have no trouble solving for $A$ and $B$.

-
can you please tell the corresponding F(n) with F(1) = 1 and F(2) = 3 – Raj Jul 7 '12 at 19:40
@Raj: you don't know how to derive it yourself? – J. M. is back. Jul 7 '12 at 19:47
@Brian and J.M : Thanks you so much for your help.It means a lot to me. – Raj Jul 7 '12 at 20:10

$$F(n)=2F(n−1)+2F(n−2)=2(F(n-1)+F(n-2))$$

Gives us the recurrence relation

$$r^n=2(r^{n-1}+r^{n-2})$$

we divide by $r^{n-2}$ to get

$$r^2=2(r+1) \implies r^2-2r-2=0$$

which is our characteristic equation. The characteristic roots are

$$\lambda_1=1-\sqrt{3} \\ \lambda_2=1+\sqrt{3}$$

Thus (because we have two different solutions)

$$F(n)=c_1 \lambda_1^n+c_2\lambda_2^n = c_1(1-\sqrt{3})^n+c_2(1+\sqrt{3})^n$$

Where $c_1$ and $c_2$ are constants that are chosen based on the base cases $F(n)$.

Brian M. Scott's answer explains how to obtain $c_1$ and $c_2$.

-

Any solution sequence can be written, with real constants $A,B,$ as $$A \; \left(1 + \sqrt 3 \right)^n + B \; \left(1 - \sqrt 3 \right)^n.$$

The set of such sequences is a vector space over $\mathbb R,$ of dimension 2. The expression below shows a linear combination of basis elements for the vector space.

In comparison, suppose we took $$G(n) = 8 G(n-1) - 15 G(n-2).$$ Then, with real constants $A,B$ to be determined, we would have $$G(n) = A \cdot 5^n + B \cdot 3^n$$

-

Define $g(z) = \sum_{n \ge 0} F(n + 1) z^n$, write the recurrence as: $$F(n + 3) = 2 F(n + 2) + 2 F(n + 1) \qquad F(1) = 1, F(2) = 3$$ Multiply the recurrence by $z$, sum over $n \ge 0$ and get: $$\frac{g(z) - F(1) - F(2)}{z^2} = 2 \frac{g(z) - F(1)}{z} + 2 g(z)$$ Solve for $g(z)$: $$g(z) = \frac{1 + z}{1 - 2 z - 2 z^2} = \frac{2 + \sqrt{3}}{2 \sqrt{3}} \cdot \frac{1}{1 - (1 + \sqrt{3}) z)} + \frac{2 - \sqrt{3}}{2 \sqrt{3}} \cdot \frac{1}{1 + (1 - \sqrt{3})z}$$ Two geometric series: $$T(n+ 1) = \frac{2 + \sqrt{3}}{2 \sqrt{3}} \cdot (1 + \sqrt{3})^n + \frac{2 - \sqrt{3}}{2 \sqrt{3}} \cdot (1 - \sqrt{3})^n$$

-