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. 
I would appreciate your help.
 A: 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}$$
A: Another standard method is the matrix method, which is the same as the Fibonacci sequence but with different starting vector. The same solution applies.
A: 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$.
A: 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.
A: (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.
