Solve $2a_n=a_{n-1}+2^n$, $a_0=1$, for all $n \geq 1$
Here is my attempt:
Let $G(x) = \sum_\limits{n=0}^\infty a_n x^n$, then we have
$$2 \underbrace{\sum_\limits{n=1}^\infty a_n x^n}_{G(x)-a_0 x^0} = \underbrace{\sum_\limits{n=1}^\infty a_{n-1} x^n}_{x(a_0+a_1x+\cdots)=xG(x)} + \underbrace{\sum_\limits{n=0}^\infty 2^n x^n}_{\frac{1}{1-2x}}$$
which leads to
$$2 (G(x)-\underbrace{a_0x^0}_{=1}) = xG(x) + \frac{1}{1-2x}$$
simplifying
$$2G(x)-xG(x)=\frac{1}{1-2x} + 2 \iff G(x)(2-x)=\frac{3-4x}{1-2x}$$
and we get
$$G(x)=\frac{3-4x}{(1-2x)(2-x)}$$
now, with partial fractions I get
$$G(x) = \frac{2}{3}\frac{1}{1-2x} + \frac{5}{3}\frac{1}{2-x}$$
So the first summand should be $\frac{2}{3}2^n=\frac{1}{3} 2^{n+1}$ but I can't figure what is the 2nd summand, that is, $\frac{1}{2-x}$. I solved this using homogenous and particular solutions and I get $a_n = \frac{1}{3} 2^{n+1} + \frac{1}{3} \frac{1}{2^n}$, which I checked for $n=1$ and it looked good, also the first summand is the same as here. How to finish this, can you see the mistake? Thanks
Best Answer
After the correction mentionned in comment, $$2G(x)-xG(x)=\frac{2x}{1-2x} + 2 \iff G(x)(2-x)=\frac{2-2x}{1-2x}$$ $$ \iff G(x)=\frac{1-x}{(1-x/2)(1-2x)}$$ $$ \iff G(x)=\frac{2/3}{1-2x}+\frac{1/3}{1-x/2} $$ hence $$a_n=\frac{2^{n+1}}3+\frac1{3\cdot2^n}.$$
A more elementary method is to find first a particular solution of the recurrence of the form $x_n=\alpha2^n$ ($2\alpha2^n=\alpha2^{n-1}+2^n\iff\alpha=\frac23$), and notice that $(a_n-x_n)$ is then a geometric sequence with ratio $\frac12$, i.e. $a_n=\frac232^n+\frac c{2^n}$, with $c=a_0-\frac23=\frac13$.