Mathacadabra
Home > Discussions > Combinatorics
Note: this page uses MathJax for formatting, so may take a few seconds to load.


Adventures with Generating Functions I

Note: This is the first of a planned 5-part series on generating functions.

First Adventure: An Infinite Sum

Let $\{F_n\}$ be the famous Fibonacci sequence defined by the recurrence formula \[ F_0=0, \; F_1=1, \; F_n=F_{n-1}+F_{n-2}, \; \mbox{for} \;\, n \geq 2. \] Thus \[ \{F_n\}=\{0,1,1,2,3,5,8,13,\ldots\}. \] How can we evaluate the infinite sum \[ \sum_{n=1}^{\infty}\frac{nF_n}{2^n} \,? \]

We suspect that this problem is an instance of a more general calculation. The more general calculation arises in terms of a generating function, which is an infinite power series whose coefficients are the terms of a sequence of interest. For example, if our sequence is $a_0,a_1,a_2,a_3\ldots$, the generating function is defined to be \[ \sum_{n=0}^{\infty}a_nx^n = a_0+a_1x+a_2x^2+a_3x^3+\cdots \] The sequence of interest here is the Fibonacci sequence; thus the generating function is \[ f(x)=\sum_{n=0}^{\infty}F_nx^n =x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots. \]

We would like to express this function in a different, useful way. So we multiply the generating function by $x$ and then by $x^2$, and perform a bit of magic: \begin{align*} xf(x) &= x^2+x^3+2x^4+3x^5+5x^6+8x^7+13x^8+\cdots\\ x^2f(x) &= x^3+x^4+2x^5+3x^6+5x^7+8x^8+13x^9+\cdots. \end{align*} Subtracting these two equations from the equation for $f(x)$, we have \begin{align*} f(x)-xf(x)-x^2f(x)&=x+x^2+2x^3+3x^4+5x^5+\cdots\\ &-(0+x^2+x^3+2x^4+3x^5+\cdots)\\ &-(0+0+x^3+x^4+2x^5+\cdots) \end{align*} Note that the terms on the right, for $n\ge2$, are of the form $(F_n-F_{n-1}-F_{n-2})x^2$, so almost all of the terms on the right cancel out (because of the Fibonacci recurrence), and we obtain \[ (1-x-x^2)f(x)=x. \] Thus the Fibonacci sequence has the generating function \[ f(x)=\frac{x}{1-x-x^2}. \] If you think about this trick, you should be able to convince yourself that similar magic is always possible for sequences satisfying a linear recurrence relation with constant coefficients. Therefore, such sequences always have a rational generating function, one which is the quotient of two polynomials.

Notice that the denominator takes its form from the Fibonacci recurrence. In the recurrence, replace $F_n$ by $1$, $F_{n-1}$ by $x$, and $F_{n-2}$ by $x^2$. Putting all the terms on one side, we get the denominator polynomial. The numerator is the polynomial obtained by multiplying the denominator by the original generating function and keeping only terms of degree less than $2$.

Now the roots of the polynomial in the denominator are $\phi=\frac{1+\sqrt{5}}{2}\approx 1.6$ and $\hat{\phi}=\frac{1-\sqrt{5}}{2}\approx -0.6$. The number $\phi$ is the famous golden ratio. Using this, we can get a partial fractions decomposition \[ f(x)=\frac{\frac{1}{\sqrt{5}}}{1-\phi x}-\frac{\frac{1}{\sqrt{5}}}{1-\hat{\phi} x}. \] Invoking geometric series, we obtain \[ f(x)=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}(\phi x)^n-\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}(\hat{\phi} x)^n. \] For the series to converge, it is necessary and sufficient that $|x| < 1/\phi$. By looking at the coefficient of $x^n$, we obtain an explicit formula for the $n$th Fibonacci number: \[ F_n=\frac{\phi^n-\hat{\phi}{\,}^n}{\sqrt{5}}, \quad \mbox{for} \; \, n \geq 0. \]

To find our infinite sum from the generating function, we take a derivative with respect to $x$ (to bring down the $n$), multiply by $x$ (to make the power of $x$ match the subscript of $F_n$), and let $x=1/2$ (to put the term $2^n$ in the denominator). The sum is \[ \sum_{n=1}^{\infty}\frac{nF_n}{2^n}=\left.\left(x\frac{d}{dx}\left(\frac{x}{1-x-x^2}\right)\right)\right|_{x=\frac{1}{2}}=\left.\frac{x(x^2+1)}{(1-x-x^2)^2}\right|_{x=\frac{1}{2}}=10. \]

Can you calculate this sum without using generating functions?

The other articles in the series:

References
  1. This sum above is given in Thomas Koshy , Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, New York, 2001.
  2. For a comprehensive explanation of generating functions, see Herbert. S. Wilf , Generatingfunctionology: Third Edition , A K Peters/CRC Press, 2005.