Closed form solution of Fibonacci-like sequence

Question

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?

Answer 1

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$.

Answer 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 $$

Answer 3

$$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$.