Finding the general formula for a sequence:

Question

I have a sequence:

$a_0 = 0;\ \ a_1 = 4;\ \ a_2 = 9; \ \ a_n = 4a_{n-1} - 5a_{n-2} + 2a_{n-3}$

I want to find the general formula.

Answer 1

$\lambda^n = 4\lambda^{n-1} - 5\lambda^{n-2} + 2\lambda^{n-3}$

$\lambda^3 - 4\lambda^2 + 5\lambda - 2 = (\lambda - 2)(\lambda -1)^2$

$\lambda_1 = 2; \ \lambda_{2,3} = 1$

$a_n = \alpha(\lambda_1)^n + \beta(\lambda_2)^n + \gamma\cdot n(\lambda_3)^n$

$a_0 = 0 = \alpha + \beta$

$a_1 = 4 = 2\alpha +\beta +\gamma$

$a_2 = 9 = 4\alpha +\beta +2\gamma$

$\alpha = 1; \beta = -1; \gamma = 3$

$a_n = 2^n +3n - 1$

Answer 2

HINT: Note that for all $n\in\Bbb{N}$ you have $$\begin{pmatrix}a_{n+3}\\ a_{n+2}\\ a_{n+1}\end{pmatrix} =\begin{pmatrix}4&-5&2\\1&0&0\\0&1&0\end{pmatrix} \begin{pmatrix}a_{n+2}\\ a_{n+1}\\ a_n\end{pmatrix}.$$

Answer 3

These are called linear difference equations. Solve the characteristic equation and use the initial values to find the appropriate constants. After, working it out, the solution to your problem is $2^n+3n-1$.