Solving functional equation for generating function Find the functional equation for the generating function whose coefficients satisfy $$
a_n = \sum_{i=1}^{n-1}2^ia_{n-i}, \text{ for } n\ge 2, a_0 = a_1 = 1
$$
This is what I've tried so far:
$$
\begin{align}
g(x) -1 -x &= \sum_{n\ge2} \sum_{i=1}^{n-1} 2^i a_{n-i}\\
&=\sum_{n\ge2} \sum_{i=1}^n 2^i a_{n-i}x^n\\
\end{align}
$$
at which point I'm stuck. How do I proceed?
 A: HINT: Note that the inner sum looks an awful lot like the coefficient of $x^n$ in the Cauchy product of $$g(x)=\sum_{n\ge 0}a_nx^n$$ and the known series
$$f(x)=\sum_{n\ge 0}2^nx^n\;.$$ 
It’s missing a couple of terms, but we can adjust for that. First note that because $\sum_{k=1}^{n-1}2^ka_{n-k}=0$ when $n<2$, the recurrence is actually $$a_n=\sum_{k=1}^{n-1}2^ka_{n-k}+[n=0]+[n=1]\;,$$ where the last two terms are Iverson brackets. Thus,
$$\begin{align*}
f(x)g(x)&=\sum_{n\ge 0}\sum_{k=0}^n2^ka_{n-k}x^n\\\\
&=1+3x+\sum_{n\ge 2}\left(2^0a_n+\sum_{k=1}^{n-1}2^ka_{n-k}+2^na_0\right)x^n\\\\
&=1+3x+\sum_{n\ge 2}(a_n+a_n+2^n)x^n\\\\
&=1+3x+\sum_{n\ge 2}(2a_n+2^n)x^n\\\\
&=1+3x+2g(x)+f(x)-(3+4x)\\\\
&=2g(x)+f(x)-x-2\;.
\end{align*}$$
Since you presumably know a closed form for $f(x)$, it should now be easy to get what you want.
A: Let
$$g(x) = \sum_{k=0}^{\infty} a_k x^k$$
From the defining recurrence:
$$\begin{align}a_2 x^2 &= 2 a_1 x^2\\ a_3 x^3 &= 2 a_2 x^3 + 4 a_1 x^3\\a_4 x^4 &= 2 a_3 x^4 + 4 a_2 x^4 + 8 a_1 x^4\\a_5 x^5 &= 2 a_4 x^5 + 4 a_3 x^5 + 8 a_2 x^5 + 16 a_1 x^5\\ \ldots \end{align}$$
and so on.  We then form 
$$g(x) - a_0 - a_1 x = \sum_{k=2}^{\infty} a_k x^k$$
by summing the above terms.  By rearranging like coefficients, we get
$$\begin{align}\sum_{k=2}^{\infty} a_k x^k &= \frac{1}{2} a_1 \sum_{k=2}^{\infty}(2 x)^k +  \frac{1}{4} a_2 \sum_{k=3}^{\infty}(2 x)^k + \frac{1}{8} a_3 \sum_{k=4}^{\infty}(2 x)^k+\ldots\\ &= (2 x^2 a_1 + 2 x^3 a_2 + 2 x^4 a_3 + \ldots) \sum_{k=0}^{\infty} (2 x)^k \\ &= \frac{2 x}{1-2 x}\sum_{k=1}^{\infty} a_k x^k \end{align}$$
Using the initial conditions and the definition of $g$, we get the following functional equation:
$$g(x) - (1+x) = \frac{2 x}{(1-2 x)} [g(x) - 1] $$
Doing this algebra, we get Marvis's result:
$$g(x) = \frac{1-3 x - 2 x^2}{1-4 x}$$
A: We have
\begin{align}
g(x) & = \sum_{n=0}^{\infty} a_n x^n = 1 + x + \sum_{n=2}^{\infty} \sum_{i=1}^{n-1} 2^i a_{n-i}x^n = 1 + x + \sum_{i=1}^{\infty} \sum_{n=i+1}^{\infty} 2^i a_{n-i} x^n\\
& = 1+x+\sum_{i=1}^{\infty} \sum_{k=n-i=1}^{\infty} 2^i a_{k} x^{k+i} = 1+x + \sum_{i=1}^{\infty} \sum_{k=1}^{\infty} (2x)^i a_{k} x^{k}\\
& = 1 + x + \dfrac{2x}{1-2x} \cdot (g(x)-1)
\end{align}
This gives us
$$\dfrac{1-4x}{1-2x} \cdot g(x) = 1+x - \dfrac{2x}{1-2x} = \dfrac{1+x-2x-2x^2-2x}{1-2x}$$
This gives us
$$\color{red}{g(x) = \dfrac{1-3x-2x^2}{1-4x}}$$
Now let us simplify this to get the coefficients,
$$g(x) = \dfrac{1-3x-2x^2}{1-4x} = (1-3x-2x^2) \left(\sum_{k=0}^{\infty}(4x)^k\right) = \sum_{k=0}^{\infty} \left(4^k x^k - 3\cdot 4^k x^{k+1} - 2^{2k+1}x^{k+2}\right)$$
Hence,
\begin{align}
g(x) & = 1 +4x + \sum_{k=0}^{\infty} 4^{k+2} x^{k+2} - 3 x - \sum_{k=0}^{\infty}\left(3 \cdot 4^{k+1} x^{k+2} + 2^{2k+1} x^{k+2} \right)\\
& = 1 + x  + \sum_{k=0}^{\infty} 2^{2k+1}x^{k+2} = 1 + x + \sum_{k=2}^{\infty} 2^{2k-3} x^k
\end{align}
Hence, we get that
$$\color{red}{a_k = 2^{2k-3}}$$
Note that we can verify that
$$\sum_{i=1}^{n-1} 2^i a_{n-i} = \sum_{i=1}^{n-2} 2^i 2^{2n-2i-3} + 2^{n-1} \cdot a_{1} = 2^{2n-3}  - 2^{n-1} + 2^{n-1} = a_n$$ for $n \geq 2$.
