How do I find the general formula of this non-geometric/arithmetic sequence? Been staring at this for a few hours and I really need some help. The sequence is:
{4, 28, 148, 700, 3124, ...} 
According to google, the formula is: $$4(4^n - 3^n)$$
But I have zero idea how to come up with this on my own. 
Any help or clues on how to solve this would be appreciated.
Thank you!
 A: The formula would be correct if the sequence obeyed
$$ x_{n+2} = 7 x_{n+1} - 12 x_n. $$
You can check that. 
As far as a method, the relevant one is the "number wall" method in Conway and Guy, The Book of Numbers





A: Will Jagy has maybe found the recurrence $$u_{n+2}=7u_{n+1}-12u_n $$ by noting that $4$ and $3$ (which are taken to the power $n$ in your formula) are the roots of $(x-4)(x-3)=x^2-7x+12=0$ explaining (...) the coefficients $7$ and $12$ of this second order recurrence, that can hardly be found by intuition.
In fact, it is not mysterious. Here is an explanation. (See also this reference)
A linear second order recurrence relationship with constant coefficients:
$$u_{n+2}=au_{n+1}+bu_n \ \ \text{with given} \ \  u_0, u_1$$
has, for its general term, an explicit expression:
$$u_n=Ar_1^n+Br_2^n,$$
where $r_1$ and $r_2$ are solutions of the quadratic equation $r^2-ar-b=0$ (under the condition that its discriminant $\Delta \neq 0$), $A,B$ being constants obtained by considering the first values of the sequence (here $A=4$ and $B=-4$.)
(this result can be proven, e.g., by recurrence on $n$.)
Remark: This method of solution "by solving a characteristic equation" is very akin to the way one solves linear differential equations with constant coefficients like $y''-7y'+12y=0$ associated with certain initial conditions.
