3

Consider (for fixed $r$) the following function: $$f(z) = \frac{1}{1-z-z^2-\cdots-z^r} = \frac{1}{1-z\frac{1-z^r}{1-z}}=\sum_{j=0}^\infty\left(z\frac{1-z^r}{1-z}\right)^j$$ (Assume everything is ok with regards to convergence.)

The text I am reading claims that if we were to write $f(z)$ in the form $\sum_{n=0}^\infty A_n z^n$, that $$A_n = \sum_{j,k} (-1)^k \binom{j}{k}\binom{n-rk-1}{j-1}$$

I have no idea where this comes from. Could anyone point me in the right direction? Thanks!

Edit: Also, the text states without explanation that in the case $r=2$, the coefficients are the Fibonnaci numbers:

$$\frac{1}{1-z-z^2} = 1 + z + 2z^2 + 3z^3 + 5z^4 + 8 z^5 + 13 z^6 + \cdots$$

Is this a non-trivial result, or am I just not seeing something?

angryavian
  • 89,882
  • Do you at least agree with the equation in the first line? – Calvin Lin May 26 '13 at 21:57
  • With regards to your edit, you can show that the generating function for the fibonacci numbers is $\frac{1}{1-x-x^2}$, which is what you are stating. – Calvin Lin May 26 '13 at 21:58
  • @CalvinLin I am ok with everything in the first line, although I hope I didn't make a mistake there (the last equality is my work). I don't understand what you mean in your second comment; could you please elaborate? Thanks! – angryavian May 26 '13 at 22:01
  • 1
    Consider the generating function of the fibonacci numbers. Since $F_{n+2} = F_{n+1} + F_{n}$, it follows that $f(x) - x f(x) - x^2 f(x) = 1$. – Calvin Lin May 26 '13 at 22:15
  • Thanks for explaining the Fibonacci part! No, $r$ is fixed. – angryavian May 26 '13 at 22:20

1 Answers1

5

$$f(z) = \sum_{j=0}^\infty \left( z \frac{1 - z^r}{1-z} \right)^j = \sum_{j=0}^{\infty}z^j \left( \sum_{k=0}^j {j\choose k} (-z^r)^k \right) \left( \sum_{m=0}^{\infty} {m+j-1 \choose j-1}z^m \right)$$

Change the order of summation. Note that in order to get a term of $z^n$, we need $j + rk + m = n$, or that $m= n - rk - j$.

The coefficient of $z^n$ is thus

$$ \sum_{j,k} (-1)^k {j\choose k} {n-rk-1 \choose j-1}$$

Let $g(x)$ be the generating function of the Fibonacci numbers. Then,

$\begin{array}{l l l l l l} g(x) &= 1 &+ x & + 2 x^2 & + 3x^3 & + \ldots \\ xg(x) & = & + x & + x^2 & + 2x^2 & + \ldots \\ x^2 g(x) & = & & + x^2 & + x^3 & + \ldots \\ \hline (1-x-x^2)g(x) & = 1 \\ \end{array}$

Hence, $g(x) = \frac{1}{1-x-x^2}$.

Note: This is with $F_1=1, F_2=2$. Depending on how you want to start your Fibonacci sequence, some people use $g(x) = \frac{x}{1-x-x^2}$ as the generating function instead.

angryavian
  • 89,882
Calvin Lin
  • 68,864