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$?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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\;.$$