Find the big-O of the sequence $a_{0} = a_{1} = 1, a_{n} = 2a_{n - 1} - 2a_{n - 2}$

Question

Find the big-O of the sequence $a_{0} = a_{1} = 1, a_{n} = 2a_{n - 1} - 2a_{n - 2}$

I found the generating function in format of $A/B$. $B = (1 - 2x + 2x^2)$ Unfortunately, the roots are complex. How can I find the big-O of $a_{n}$ when $n$ goes to $∞$.

Answer 1

The roots of $x^2-2x+2=0$ are $\lambda_{1,2}=1\pm i$, and hence the general term of the form $$ a_n=c_1 (1+i)^n+c_2 (1-i)^n $$ In fact, $c_1=c_2=1/2$ and hence $$ a_n=2^{n/2-1} \left( \mathrm{e}^{i n\pi/4}+\mathrm{e}^{-in\pi/4} \right)=2^{n/2}\cos(n\pi/4)=\mathcal O(2^{n/2}) $$