2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – AlanH Apr 11 '13 at 5:14
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Apr 11 '13 at 5:17
  • $\begingroup$ But doesn't that change the value of the sum? $\endgroup$ – AlanH Apr 11 '13 at 5:26
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Apr 11 '13 at 5:29
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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}$$ $\endgroup$ – vonbrand Apr 16 '13 at 19:22
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.