3

When attempting to find an easy answer to this question

What is the coefficient of $x^{11}$ in the power series expansion of $\dfrac 1{1-x-x^4}$?

I'd think of $\frac{1}{1-x-x^4}$ as of a generating function. I did some series expansion on WA and 'googled' the sequence on oeis. It's http://oeis.org/A003269 .
$$a(n) = a(n-1) + a(n-4)\text{ with }a(0) = 0, a(1) = a(2) = a(3) = 1.$$

So the question is: why does this happen? I.e. I need some explanation why is $\dfrac{1}{1-s-s^4}$ the generating function for the sequence above.

Community
  • 1
Alexey Burdin
  • 5,214

2 Answers2

3

More generally, consider a generating function $$ f(x) = \frac{P(x)}{Q(x)}$$ where $P(x)$ and $Q(x)$ are polynomials. Write $Q(x) = q_0 + q_1 x + \ldots + q_d x^d$. Thus $P(x) = f(x) Q(x)$. If $f(x) = a_0 + a_1 x + \ldots$, then the coefficient of $x^n$ in $f(x) Q(x)$ is $a_{n-d} q_d + \ldots +a_{n} q_0$, so if $n$ is greater than the degree of $P(x)$, this must be $0$.

Michael Hardy
  • 1
Robert Israel
  • 448,999
2

If $a(n)$ are coefficients of a power series $f(x)=\sum a(n)x^n$, then multiplying by $x^k$ gives $$x^kf(x)=\sum_{n=0}^\infty a(n)x^{n+k}=\sum_{n=-k}^\infty a(n-k)x^n$$ So if you start with

  • $a(n)=a(n-1)+a(n-4)$,
  • defining $a(n)$ to be $0$ for negative $n$

then the recurrence almost still holds for small $n$ when $a(0)=0$ and $a(1)=a(2)=a(3)=1$. The recurrence fails for $n=1$ though. This tells us $$\sum_{n=-4,n\neq1}^\infty a(n)x^n=\sum_{n=-4,n\neq1}^\infty a(n-1)x^n+\sum_{n=-4,n\neq1}^\infty a(n-4)x^n$$ $$\implies \sum_{n=-4}^\infty a(n)x^n-x=\sum_{n=-4}^\infty a(n-1)x^n+\sum_{n=-4}^\infty a(n-4)x^n$$ $$\implies f(x)-xf(x)-x^4f(x)=x$$ which implies $f(x)=\frac{x}{1-x-x^4}$ for $x$ in the interval of convergence. Since power series for rational functions like this are unique, if you now start with the rational function $\frac{x}{1-x-x^4}$, it must have this sequence $a(n)$ as its power series coefficients.

Your function is this one divided by $x$, so indices all shift by $1$. You have the right recurrence for $\frac{1}{1-x-x^4}$, but note that your indices are off. For instance, you have $a(0)=0$, but for $\frac{1}{1-x-x^4}$, the constant term is clearly $1$.

2'5 9'2
  • 54,717