Solving functional equation for generating function

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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