Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.