Closed-form representation of the following recursively defined sequence

Question

Trying to find a closed-form representation of the following recursively defined sequence:

$a_{0}=1, a_{1}=2, a_{n+2}= a_{n+1} +2a_{n}$.

Afraid that I am a little out of my depth here, i know i can use induction to prove but i don't know where to start.

Answer 1

Rabbit out of a hat:From $a_{n+2}=a_{n+1}+2 a_n$ we have the associated polynomial $x^2=x+2$, whose solutions are $x_0=2$ and $x_1=-1$. Therefore $a_n = A x_0^n +B x_1^n = A .2^n+B (-1)^n$ with constants $A,B.$ When $ n=0$ we have $A+B=1, $ and when $n=1$ we have $2 A-B=2. $ Hence $A=1$ and $ B=0 $ and $$a_n =2^n.$$ JUSTIFICATION: (1) If $f(n) =x^n$ and $x^2=x+2$ then $f(n+2)=f(n+1)+2 f(n)$....(2)Therefore any $g(n)=A x_0^n+B x_1^n$ with constants $A,B$ satisfies $ g(n+2)=g(n+1)+2 g(n)$....(3) Take constants $A,B$ for which $g(0)=1=a_0$ and $g(1)=2=a_1. $ Then the function $h(n)=g(n)-a_n$ satisfies $ h(n+2)=h(n+1)+h(n)$ with $ h(0)=h(1)=0 $ so $h(n)=0$ for all $n$....So $a_n=g(n)=2^n$.

Answer 2

The recursion is inconsistent because $a_{n+2}=a_{n+1}$ and $a_{n+1}=2a_n$ cannot both hold for all $n$ (or all $n$ after some initial values).

The sequence $1,2,2,4,4,8,8,16,16,\dots$ with the indexing as in the question is given by $2^{\lfloor \frac{n}{2} \rfloor}$.

Assuming you know how to solve the recursion $b_{i+1}=2b_i$, the problem amounts to the fact that a function of integers with $f(2k)=f(2k+1)$ for all $k$ can be written as a function of ($n$ DIV 2), and that integer division operation DIV can be written using the Greatest Integer function $\lfloor x \rfloor$.