Let $(a_n)_{n\geq 1}$ be a sequence of integers defined by $a_1=1, a_2=2$, and for each $n\geq 1$, $a_{n+2} =a_{n+1} +3a_n$. I am trying to learn how to write out the equations correctly. Sorry in advance. 
Let $(a_n)_{n\geq 1}$ be a sequence of integers defined by $a_1=1, a_2=2$, and or each $n\geq 1$, $a_{n+2} =a_{n+1} +3a_n$. Find the formula for an for each $n\geq 1$. 
I'm not sure what to do to prove the basic step. If I say $n=1$ I get values that I do not know? 
And for the inductive step...I would say n=k+1? 
 A: You can begin by writing explicitly down the first few terms of the sequence and guessing the right formula for $a_n$.
For example, you have:
$$\begin{split} a_1 &= 1\\ a_2 &= 2\\ a_3 &= a_2 + 3 a_1\\ &= 5\\ a_4 &= a_3 + 3a_2\\ &= 11 \\ a_5 &= a_4 + 3a_3 \\ &= 26 \\ a_6 &= a_5 + 3 a_4 \\ &= 59\end{split}$$
and it looks like an exponential growth is going on here. Therefore, you can conjecture $a_n=\lambda^n$ (with $\lambda\neq 0$, obviously) and try to find the right $\lambda$ using the equation.
Plugging $a_n=\lambda^n$ in $a_{n+2} = a_{n+1} + 3 a_n$ yields:
$$\lambda^{n+2} = \lambda^{n+1} + 3\lambda^n\; ,$$
that is:
$$\lambda^2 - \lambda - 3=0$$
and gives two possible values for $\lambda$, i.e.:
$$\tag{1} \lambda_1 = \frac{1-\sqrt{13}}{2}\quad \text{and}\quad \lambda_2 = \frac{1+\sqrt{13}}{2}\; ,$$
such that the sequences $(\lambda_1^n)$ and $(\lambda_2^n)$ are both solutions of the recurrence equation.
Instead of choosing one of the $\lambda$s found above, now you look at the equation and realize that it is linear, for if $(a_n)$ and $(b_n)$ are two of its solutions also $(A\cdot a_n+B\cdot b_n)$ (with $A,B\in \mathbb{R}$) is a solution. Therefore, any sequence of the type:
$$\tag{2} a_n=A\cdot \lambda_1^n + B\cdot \lambda_2^n$$
is a solution of your recurrence equation.
Finally, now you choose the two parameters $A$ and $B$ in such a way that the sequence (2) satisfy the initial conditions $a_1=1$ and $a_2=2$. Plugging (2) into the initial conditions yields:
$$\begin{cases} A\cdot \lambda_1 + B\cdot \lambda_2 = 1\\ A\cdot \lambda_1^2 + B\cdot \lambda_2^2 = 2\end{cases}$$
which is a linear system of equations in the unknowns $A$ and $B$, whose solution is:
$$\begin{split} A &= \frac{\lambda_2 - 2}{\lambda_1\lambda_2-\lambda_1^2}\\ B &= \frac{2-\lambda_1}{\lambda_2^2 - \lambda_1\lambda_2}\; . \end{split}$$
Hence:
$$\begin{split} a_n &= \frac{\lambda_2 - 2}{\lambda_1\lambda_2-\lambda_1^2}\cdot \lambda_1^n + \frac{2-\lambda_1}{\lambda_2^2 - \lambda_1\lambda_2}\cdot \lambda_2^n\\ &= \frac{\lambda_2 - 2}{\lambda_2-\lambda_1}\cdot \lambda_1^{n-1} + \frac{2-\lambda_1}{\lambda_2 - \lambda_1}\cdot \lambda_2^{n-1}\end{split}$$
with $\lambda_{1,2}$ given by (1) is the solution of the IVP for your recurrence equation.
