<s>[INST] 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?
 [/INST] 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$.
</s>