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

-

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.

-
Yeah, I've been trying to figure out how to get the indices to start at $0$ all day. Why is it you can just start the the indices (in your hint) at $0$? –  AlanH Apr 11 '13 at 5:14
@Alan: Which ones? The $n$s automatically do so. The inner sum with index $k$ doesn’t match the one that you’re given, but we know what the missing terms are: they’re $2^0a_n$ and $2^na_0$, so I just add them to $\sum_{k=1}^{n-1}2^ka_{n-k}$ to get the sum from $k=0$ to $k=n$. –  Brian M. Scott Apr 11 '13 at 5:17
But doesn't that change the value of the sum? –  AlanH Apr 11 '13 at 5:26
@Alan: You know that $$\sum_{k=1}^{n-1}2^ka_{n-k}=a_n\;,$$ so $$\sum_{k=0}^n2^ka_{n-k}=2^0a_n+\sum_{k=1}^{n-1}2^ka_{n-k}+2^na_0=a_n+a_n+2^n=2a‌​_n+2^n\;;$$ I’ve not changed anything. And $\sum_{k=0}^n2^ka_{n-k}$ is the coefficient that arises naturally in the product $fg$. –  Brian M. Scott Apr 11 '13 at 5:29

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

-
Why all that mess... maxima tells me that:$$\frac{1 - 3 x - 2x^2}{1 - 4x} = \frac{7}{8} + \frac{1}{2} x + \frac{1}{8} \frac{1}{1 - 4 x}$$ Thus $$a_n = \frac{7}{8} [n = 0] + \frac{1}{2} [n = 1] + \frac{1}{8} \cdot 4^n = \frac{7}{8} [n = 0] + \frac{1}{2} [n = 1] + 2^{2 n - 3}$$ –  vonbrand Apr 16 '13 at 19:22

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

-