Solving recurrence relations of n rabbits on island Okay so one pair of rabbits is left in an island. 
After 1 month it produces 2 pairs of rabbits, and 2 months or older they produce 6 every month.
I came up with the recurrence relation
$ A_{n} = 2(A_{n-1} - A_{n-2}) + 6A_{n-2} + A_{n-1} $
For n >= 2,
Which finds the total pairs of rabbits on the island after n months (rabbits never die)
My problem is that the next problem says to solve it in terms of just n and I have been breaking my head but can't make any progress.... for example the equation have a format of just n:
$ A_{n} = 2n^n + 6n^n + n$
How does one solve this problem?
 A: The recurrence relationship was found correctly:
$$ A_n = 2(A_{n-1} - A_{n-2}) + 6A_{n-2} + A_{n-1} $$
Collecting like-terms and setting $A_n = r^n$ produces the characteristic equation:
$$ r^2 - 3r - 4 = 0 $$
whose (nonzero) roots are $r = 4,-1$.
We can set up a system of two linear equations to find coefficients of the geometric sequences that match our initial conditions, $A_n = (4^n)C_1 + (-1)^n C_2$.  
The OP expressed doubt that the initial conditions $A_0 = 1,A_1 = 3$ would provide a correct solution, so let's use the terms $A_2 = 13,A_3 = 51$:
$$ (4^2)C_1 + (-1)^2 C_2 = 13 $$
$$ (4^3)C_1 + (-1)^3 C_2 = 51 $$
Subtracting $4$ times the first equation from the second equation gives:
$$ (-1 - 4)C_2 = 51 - 52 = -1 $$
Therefore $C_2 = 1/5$, and substituting this into either of the two original equations allows us to solve for $C_1 = 4/5$.
Note that the solution is valid for both of the terms $A_0,A_1$ as well:
$$ (4^0)C_1 + (-1)^0 C_2 = 1 = A_0 $$
$$ (4^1)C_1 + (-1)^1 C_2 = 3 = A_1 $$
So we could have gotten the same coefficients using these smaller terms.
