Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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. 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. 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. Jul 7 '12 at 19:43

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer
    
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. 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$.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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