# How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve.

Find a formula for the following recurrence relation: (translated from Portuguese)

a) $a_{1}=3,a_{2}=5, a_{n+1}=3a_{n}-2a_{n-1}.$

b) $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}.$

Let me show how I solved the first one. Note that $a_{1}=3,a_{2}=5, a_{3}=9,a_{4}=17$, then $a_{n}=2^{n}+1$ for all $n\in \mathbb{N}$ (I proved it by induction on $n$), but the last one I was not able to solve.

-
Go look up "Lucas Numbers", a sequence starting with $1,3$ and $a_{n+2} = a_n+a_{n+1}$ looks like Lucas Numbers –  Jeremy Carlos Mar 16 '12 at 20:30
Did you prove your attempt for a)? –  Raphael Mar 16 '12 at 20:39
@Raphael: Yes! By induction on $n$. –  spohreis Mar 16 '12 at 20:57
i think the answer is $\frac{\alpha^{2n+2}-\beta^{2n+2}}{\sqrt5}$ where $\alpha$ and $\beta$ you can get from Andre Nicolas's suggestion. –  Lorenz Chaos Mar 16 '12 at 21:09

There is a standard method which is sketched below. Forget about the initial conditions $a_1=1$, $a_2=3$ for now. We look for solutions of the recurrence relation of the shape $a_n=x^n$, where $x$ is a number to be determined.

Substituting in the recurrence, we get $x^{n+2}=x^{n+1} +x^n$. Forgetting about the possibility $x=0$, which mostly can't happen, this reduces to $x^2-x-1=0$. Solve. We get $$x=\frac{1\pm\sqrt{5}}{2}.$$ Call the two roots $\alpha$ and $\beta$. (The number $\frac{1+\sqrt{5}}{2}$ is a famous number, often called the Golden Number. It even has two standard symbols attached to it, $\varphi$ and $\tau$.)

Now look for numbers $A$ and $B$ such that the expression $A\alpha^n+B\beta^n$ satisfies your initial conditions. (If you have studied Differential Equations, the procedure will be structurally familiar, for good reason.)

The suitable $A$ and $B$ are not hard to find. We get $A=B=1$. To check that $a_n=\alpha^n +\beta^n$ is indeed the solution, note that $A\alpha^n+B\beta^n$ satisfies our recurrence for any $A$ and $B$. Choosing $A$ and $B$ so that the initial conditions are satisfied forces the formula to be correct for all $n$.

It would have been a little more pleasant to find $A$ and $B$ if we had been given the usual initial conditions $a_0=2$, $a_1=1$. Whether we start at $a_0$ or $a_1$, the sequence is called the Lucas sequence.

Remark: Variants of this idea work for all linear homogeneous recurrences with constant coefficients. Look in particular at the recurrence $a_{n+1}=3a_n-2a_{n-1}$ that you solved successfully by thinking.

Use the same procedure. We arrive at the equation $x^2-3x+2=0$, which has roots $\alpha=2$, $\beta=1$. Now we try to find $A$ and $B$ such that $A\alpha^n+B\beta^n$ satisfies our initial conditions. So we want $A(2)+B(1)=3$, $A(2^2)+B(1^2)=5$. We get $A=1$, $B=1$. This yields the formula that you already know.

There are other general methods of doing the same thing, such as generating functions.

-

Besides Andre Nicolas approach you could also try the following: Generating functions, define (just for a little cleaner solution) $b_0=a_1$, $b_1=a_2$, and in general $b_m=a_{m+1}$.

Let $F(t)=\sum_{n=1}^\infty b_nt^n$. Then $$b_{n+2}=3b_{n+1}-2b_n$$$$b_{n+2}t^{n+2}=3b_{n+1}t^{n+2}-2b_nt^{n+2}$$Taking summation from $n=0$ to infinity: $$\sum_{i=2}^\infty b_it^i=3t\sum_{i=1}^\infty b_it^i-2t^2\sum_{i=0}^\infty b_it^i$$$$F(t)-b_1t-b_0=3t(F(t)-b_0)-2t^2F(t)$$Using the inital conditions:$$F(t)-5t-3=3t(F(t)-3)-2t^2F(t)$$$$F(t)(1-3t+2t^2)=3-4t$$Thus, $$F(t)=\frac{3-4t}{1-3t+2t^2}$$ Break it $$F(t)=\frac{2}{1-2t}+\frac{1}{1-t}$$and that $\sum x^k=\frac{1}{1-x}$ where the sum goes form $k=0$ to infinity we get:$$F(t)=2\sum (2t)^k+\sum t^k$$Thus $b_n=2(2^n)+1$

And moving it back to your initial sequence of $a_n$ you get indeed: $$\boxed{a_n=2^n+1}$$

-

Another standard method is the matrix method, which is the same as the Fibonacci sequence but with different starting vector. The same solution applies.

-

Here's a slightly ad hoc approach to your problem b): It's easy to see that $a_1 = 1 = 0+1 = F_0+F_2$ and that $a_2 = 3 = 1+2 = F_1+F_3$; since any linear combination of Fibonacci numbers satisfies the Fibonacci recurrence (proof: if $S_n=\sum_i a_i F_{n+i}$, then $S_{n-1}+S_n = (\sum_i a_i F_{n+i-1})+(\sum_i a_i F_{n+i}) = \sum_i a_i(F_{n+i-1}+F_{n+i}) = \sum_i a_iF_{n+i+1} = S_{n+1}$) then $a_n = F_{n-1}+F_{n+1}$ must hold for all $n$.

-

(I'm not sure how to write mathematical symbols here, any help appreciated) There is a really neat way of doing this easily: Say v(k) = (a(k), a(k+1)) we see that by the definition of your series, v(k+1) = A*v(k) where A = (1 1) (0 1). thus, define v(1)=(1, 3), v(k)=(A^k)*v(1). Then we diagonalize A = X^(-1)*B*X (we know how to easily diagonalize any matrices by size up to 4, if they are diagonalizable), so we see (by diagonalizing) that B= (phi 0) (0 1-phi) This way we get that: v(k) = X^(-1)*(B^k)*X*v(1) where B^k= (phi^k 0) (0 (1-phi)^k). This method works generally for any finite linear recurrence relation.

-