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.

So $a_2=a_3=2a_1=4,a_3=a_4=2a_2=8$ we have that $a_3=4$ and $a_3=2a_2=8$ — kingW3, Sep 23 '15 at 19:47
If $a_{n+2}=2a_n$ then $a_n=2^{\lceil n/2\rceil}$ and if $a_{n+1}=2a_n$ then $a_n=2^n.$ If the recursive formula is the one lulu says, then it is completely different.. — CIJ, Sep 23 '15 at 20:07
Lulu, yes i absolutely did mean write that wrong. nice catch — Pixe1, Sep 24 '15 at 19:29
What prevents you from proving that $a_n=2^n$ for every $n$, using induction? Please be specific. — Did, Sep 24 '15 at 19:51

score 1 · Answer 1 · answered Sep 23 '15 at 19:53

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

ive been trying to solve the recursion but for the life of me i cant figure this out. — Pixe1, Sep 24 '15 at 19:36

DanielWainfleet · Accepted Answer · 2015-09-25T06:41:10.567

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

Closed-form representation of the following recursively defined sequence

2 Answers2