Suppose recurrence is $a_{n+2}=a_{n+1}+6a_{n}$
Tried to solve it with solving $Fnc(n)=An^5+Bn^4+Cn^3+Dn^2+En+F$
Which gives $A = (-33/4), B = (365/4), C = (-1385/4), D = (2155/4), E = (-551/2), F = 5$
But $Fnc(0,1,2,3,4,5,6\dots)={5, 5, 35, 65, 275, 65\dots}$ and everything after 65, including it is definitely wrong.
Right sequence would be: $5, 5, 35, 65, 275, 665, 2315, 6305, 20195, 58025\dots$
Raising degree gives more correct members of sequence, yet it isnt general formula for recurrence.
What is the trick to solve this?
Replace $ a_{t} $ with $ x^{t} $
$ x^{n+2} = x^{n+1} + 6x^{n} $
$ x^{2} = x + 6 $
$ x^{2} - x - 6 = 0 $
$ (x-3)(x+2) = 0 $
Thus the recurrence is given by,
$ a_{n} = A\cdot3^{n} + B\cdot(-2)^{n} $
A & B can be found using the initial values.