1
$\begingroup$

Assume that $(a_n)^{\infty}_{n=0}$ is a sequence given by $a_0=1$ and $a_{n+1}=2a_{n}+n$ for all $n \ge 0$, what is the formula for $a_n$?

we know that $F(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots$
and our sequence is $1, 2, 5, 12, 27, 58, \dots$
to find the generating function for the sequence I started with
$F(x)=a_0+(\underline{2a_0}+\widetilde0)x+(\underline{2a_1}+\widetilde1)x^2+(\underline{2a_2}+\widetilde2)x^3+\dots$
after distributing the variables into the parenthesis, i separated the terms with $\underline{}$ and $\widetilde{}$
$\underline{} = 2a_0x+2a_1x^2+2a_2x^3+2a_3x^4+\dots$
$\underline{} = 2x(a_0+a_1x^1+a_2x^2+a_3x^3+\dots)$
$\underline{} = 2x \times F(x)$

$\widetilde{} = x^2 + 2x^3 + 3x^4 + 4x^5$
now I don't know what to do with this part, if I had used $n$ earlier instead of putting in the numbers I could just factor out $nx^2$ and get $\widetilde{} = nx^2(\frac{1}{1-x})$ but I don't think I can have $n$ when solving for the generating function of the sequence?

Any ideas of how to get past just this part?

$\endgroup$
4
  • 1
    $\begingroup$ Pull an $x^2$ out and note that $$\frac{d}{dx}\left(\frac{1}{1-x}\right)=1+2x+3x^2+4x^3+...$$ $\endgroup$ Oct 22, 2016 at 1:56
  • $\begingroup$ @Eleven-Eleven If I use your idea then I would get $F(x)=1+2xF(x)+\frac{1}{(1-x)^2}$, this equals $F(x)=\frac{(1-x)^2+1}{(1-2x)(1-x)^2}$ then I could use partial fractions to separate this into three terms with a $1-\underline{}x$ in the denominators, find a summation and find $a_n$ $\endgroup$
    – idknuttin
    Oct 22, 2016 at 2:21
  • 1
    $\begingroup$ Yes except you have $x^2$ in the numerator, not 1. $\endgroup$ Oct 22, 2016 at 2:27
  • 1
    $\begingroup$ For all things generating functions, look up Wilf's Generatingfuntionology... it is free to download online and you get all the tricks to solve such expression... $\endgroup$ Oct 22, 2016 at 2:32

3 Answers 3

3
$\begingroup$

From the recursion formula, you can guess a linear combination of $a_n$ and $n$ will be a geometric sequence, that is, you can assume $a_{n+1}-\lambda(n+1)+M=2(a_n-\lambda n+M)$ for some $\lambda$ and $M$. Put it into the the recursion formula, we can take $\lambda=-1$ and $M=1$. So we get $$a_{n+1}+(n+1)+1=2(a_n+n+1).$$

Let $b_n=a_n+n+1$, then $b_{n+1}=2b_n$, which implies that $b_n=2^nb_0$. Since $b_0=a_0+0+1=2$, then $b_n=2^{n+1}$, which implies that $$a_n=b_n-n-1=2^{n+1}-n-1.$$

$\endgroup$
1
  • $\begingroup$ Your method works. However, the op is trying to use generating functions to solve... $\endgroup$ Oct 22, 2016 at 2:02
2
$\begingroup$

My preferred approach using generating functions starts by assuming that $a_n=0$ for $n<0$ and rewriting the recurrence so that it hold for all $n\ge 0$:

$$a_n=2a_{n-1}+n-1+2[n=0]\;.\tag{1}$$

Here $[n=0]$ is an Iverson bracket, and the last term of $(1)$ ensures that $a_0=1$. Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$; if we let $g(x)=\sum_{n\ge 0}a_nx^n$ be the generating function, we have

$$\begin{align*} g(x)&=\sum_{n\ge 0}a_nx^n\\ &=2\sum_{n\ge 0}a_{n-1}x^n+\sum_{n\ge 0}nx^n-\sum_{n\ge 0}x^n+2\\ &=2x\sum_{n\ge 0}a_nx^n+x\sum_{n\ge 0}nx^{n-1}-\frac1{1-x}+2\\ &=2xg(x)+\frac{x}{(1-x)^2}-\frac1{1-x}+2\;. \end{align*}$$

Solving for $g(x)$, decomposing the resulting rational function into partial fractions, and rewriting the resulting terms as formal power series, we get

$$\begin{align*} g(x)&=\frac{x}{(1-x)^2(1-2x)}-\frac1{(1-x)(1-2x)}+\frac2{1-2x}\\ &=\frac{x-(1-x)+2(1-x)^2}{(1-x)^2(1-2x)}\\ &=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}\\ &=\frac2{1-2x}-\frac1{(1-x)^2}\\ &=2\sum_{n\ge 0}(2x)^n-\sum_{n\ge 0}(n+1)x^n\\ &=\sum_{n\ge 0}\left(2^{n+1}-n-1\right)x^n\;, \end{align*}$$

which yields the closed form

$$a_n=2^{n+1}-n-1\;.$$

$\endgroup$
1
$\begingroup$

You must note that $a_0=1$ which is unaccounted for...
Using the fact that

$$\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{1}{(1-x)^2}=1+2x+3x^2+...$$

you now should get

$$F(x)=1+2xF(x)+x^2\frac{1}{(1-x)^2}$$ $$F(x)(1-2x)=1+\frac{x^2}{(1-x)^2}$$ $$F(x)=\frac{1-2x+2x^2}{(1-2x)(1-x)^2}$$

Now use partial fraction decomposition to obtain three power series and look at the coefficients.

$\endgroup$
2
  • $\begingroup$ just making sure, it's probably a typo but shouldn't the numerator be $1-2x+2x^2$? $\endgroup$
    – idknuttin
    Oct 22, 2016 at 2:34
  • 1
    $\begingroup$ Yes.... on an iPhone so mistakes are bound... $\endgroup$ Oct 22, 2016 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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