-1
$\begingroup$

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.

  • 7
    As was [already mentioned](http://math.stackexchange.com/q/77790/6179): *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.*2011-12-26

1 Answers 1

3

You should definitely read (the first chapter of) generatingfunctionology.

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