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!
On
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.
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