# Find $a_n$ with $n\geq 0$

Let $a_1 = 1, \ a_2 = 18$ and $a_{2n} = 8a_n + 10, \ \ n\geq 1$ Find $a_n$ with $n\geq 1$

I tried to solve above problem use generating function. Can anyone help me solve by generating function.

-
the sequence is not well defined. The indices are chosen in such a way that you cannot even calculate $a_1$ and get a contradiction for $a_0$ (note $a_{2\times 0} = a_0$) –  user20266 Dec 26 '11 at 13:26
sorry, lack $a_1 = 18$ I have editted. –  qwerty89 Dec 26 '11 at 13:30
@Thomas: thank you! I have editted :D $a_1 = 1, \ a_2 = 18$. –  qwerty89 Dec 26 '11 at 13:33
ok, so you have $a_0$ and $a_1$ and the formula is probably only valid if $n>0$ (?). That is you get $a_2$ from $a_1$, no $a_3$, but $a_4$... you can only derive values for $n = 2^k$, not for any $n$. –  user20266 Dec 26 '11 at 13:35
As was already mentioned: Please start accepting answers to your earlier questions. In Math.SE, this is considered important feedback for answerers. You can accept an answer by clicking the green tick/check mark under it. –  Did Dec 26 '11 at 13:47
So... your assumption is that $b_{k+1}=ub_k+v$ with $u=8$, $v=10$, $b_0=1$, and $b_k=a_{2^k}$ for every $k\geqslant0$. Consider the generating function $$B(x)=\sum\limits_{k\geqslant0}b_kx^k.$$ The recursion on $(b_k)_{k\geqslant0}$ reads $$B(x)=b_0+\sum\limits_{k\geqslant1}b_kx^k=1+\sum\limits_{k\geqslant0}b_{k+1}x^{k+1}=1+\sum\limits_{k\geqslant0}(ub_k+v)x^{k+1},$$ hence $$B(x)=1+ux\sum\limits_{k\geqslant0}b_kx^k+vx\sum\limits_{k\geqslant0}x^k=1+uxB(x)+\frac{vx}{1-x}.$$ This yields $$B(x)=\frac{1+\frac{vx}{1-x}}{1-ux}=\frac{1-(1-v)x}{(1-x)(1-ux)}=\frac{r}{1-x}+\frac{s}{1-ux},$$ for some suitable constants $r$ and $s$. Hence, $$B(x)=r\sum\limits_{k\geqslant0}x^k+s\sum\limits_{k\geqslant0}u^kx^k,$$ which implies that, for every $k\geqslant0$, $$b_k=r+su^k.$$ To conclude, either one computes $r$ and $s$ solving the simple fraction expansion of $B(x)$, or one notes that $r+s=b_0=1$ and $r+su=b_1=u+v$, hence $r=\dfrac{v}{1-u}$ and $s=1-\dfrac{v}{1-u}$.