Finding the formula for nth term of a sequence

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.

• $x^2-4x-4=0$ has no integer solutions, but it does have solutions... Feb 16 '15 at 22:48
• I know but this should be solvable without a calculator and number are strange when it comes to this equation Feb 16 '15 at 22:49
• The above quadratic equation is solvable without a calculator...were you able to find those solutions? Feb 16 '15 at 22:50
• Quadratic equations are almost always solvable without the calculator. Feb 16 '15 at 22:51
• $2 + 2\sqrt{2}$ and $2-2\sqrt{2}$ Feb 16 '15 at 22:51

2 Answers

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"

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$$