Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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