Find the general formula of a the series. If we are given that the first 4 terms of a series are 1,2,4, and 8. And the rest of the terms are summation of the previous 4 terms i.e. 5th term is 8+4+2+1 and so on. So how can we find the general formula of the series. I was asked this question in the interview. Thank You...
 A: This sequence is similar to the Fibonacci sequence, except how it starts and that it satisfies a fourth order recurrence relation instead of one of second order, and it can be handled by the same methods.
The equation $x^4=1+x+x^2+x^3$ has four distinct roots $x_1,x_2,x_3,x_4$, which can be computed as accurately as desired. (Two of these are real, and two are complex conjugate of each other.) If we let $a_n=x_i^n$, where $x_i$ is one of the four roots above and $n=0,1,2,\dots$, then $a_n=a_{n-4}+a_{n-3}+a_{n-2}+a_{n-1}$ for all $n\geq 4$. In order to get not only the right recurrence relation, but also the right starting values, we let
$$a_n=c_1x_1^n+c_2x_2^n+c_3x_3^n+c_4x_4^n$$
for $n=0,1,2,\dots$. No matter how we choose the $c_i$, the recurrence relation above will hold for all $n\geq 4$. So we impose the conditions
$$a_0=1,\qquad a_1=2,\qquad a_2=4,\qquad a_3=8$$
which gives us a linear system with four equations for the four unknowns $c_1,\dots,c_4$. Solving this system gives us the desired formula for $a_n$. (Since we do not find nice solutions to the characteristic equation $x^4=1+x+x^2+x^3$, we do not get a very nice formula for $a_n$ in this way.)
In practice, if we want to apply this formula for some particular (large) value of $n$, we need to compute the $x_i$ with sufficient accuracy, so that we can get the correct answer by rounding the value we get for $a_n$ to the nearest integer. This may be more computational intensive than just using the recursion formula itself.
