Finding the formula for nth term of a sequence

Question

I have the following recursive sequence an i want to find the general formula for the nth term of a sequence:

$$a_{n+2}=4a_{n+1}+4a_n,a_1=1,a_2=2$$

I have the following characteristic equation: $x^2=4x+4$ but this has no integer zeroes so i do not know how to proceed with this.

Answer 1

there exists universal method of solving linear recurrences

for example in these topics

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

solving recurrence relations

Solving a Linear Recurrence Relation

it was described.

it is also in Wikipedia http://en.wikipedia.org/wiki/Recurrence_relation

or just google for "solving linear recurrence relations" or "solving homogeneous linear recurrence relations"

Answer 2

since the constants are chosen so that the surds always cancel, we can use the binomial theorem to obtain for $n \in \mathbb{N}$: $$ a_{n+1} = 2^n \sum_{0 \le 2k \le n} \binom{n}{2k} 2^k $$