Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How would you derive the generating function for a recursive sequence $$f_a = m_1f_{a-1} + m_2f_{a-2} + m_3f_{a-3} + \cdots + m_nf_{a-n}?$$ With the intial conditions
\begin{eqnarray*} f_{0} &=&0 \\ f_{1} &=&1 \\ f_{2} &=&0 \\ &&\vdots \\ f_{n-1} &=&0 \end{eqnarray*} Where $m_n$ is constant.
I've already found the generating function for a recursive sequence $$f_a = f_{a-1} + f_{a-2} + f_{a-3} + \cdots + f_{a-n}$$

Here's my work thus far:
Since $f_{0}=0,$ $f_{1}=1,$ $f_{2}=\dots =f_{n-1}=0$, and because we know that $z$ is the generating function for a sequence $(0,1,0,0, \ldots ,0)$, we have \begin{eqnarray*} F\left( z\right) &=&z+\sum_{a=n}^{\infty }f_{a}z^{a} \\ &=&z+\sum_{a=n}^{\infty }\left( m_{1}f_{a-1}+m_2f_{a-2}+\dots +m_nf_{a-n}\right) z^{a} \\ &=&z+\sum_{a=n}^{\infty }m_1f_{a-1}z^{a}+\sum_{a=n}^{\infty }m_2f_{a-2}z^{a}+\dots +\sum_{a=n}^{\infty }m_nf_{a-n}z^{a} \\ &=&z+z\sum_{a=n}^{\infty }m_1f_{a-1}z^{a-1}+z^{2}\sum_{a=n}^{\infty }m_2f_{a-2}z^{a-2}+\dots +z^{n}\sum_{a=n}^{\infty }m_nf_{a-n}z^{a-n} \\ &=&z+z\sum_{a=n-1}^{\infty }m_1f_{a}z^{a}+z^{2}\sum_{a=n-2}^{\infty }m_2f_{a}z^{a}+\dots +z^{n}\sum_{a=0}^{\infty }m_nf_{a}z^{a} \end{eqnarray*}

I know that the next step is to break the each of the functions up into terns if $F(z)$ and $z$, but I'm not sure how to do that.

share|cite|improve this question
up vote 2 down vote accepted

Take a look at Wilf's "generatingfunctionology". He gives rules for handling generating functions.

Define the generating function for the sequence $\langle f_n \rangle_{n \ge 0}$: $$ F(z) = \sum_{n \ge 0} f_n z^n $$ Then the generating function for the sequence $\langle f_{n + k} \rangle_{n \ge 0}$ is seen to be (chop off the fist $k$ terms, adjust exponents): $$ \frac{F(z) - f_0 - f_1 z - f_2 z^2 - \ldots - f_{k - 1} z^{k - 1}}{z^k} $$ If you write your recurrence as (sorry for the change in notation): $$ f_{n + k} = m_{k - 1} f_{n + k - 1} + \ldots + m_0 f_{n} $$ and apply the above relation for shifted sequences, you get a linear equation for $F(z)$, which solves into a ratio of polynomials in $z$. That one can split into partial fractions (possibly with complex coefficients), and expand each term by using the binomial theorem for negative exponents. It won't come out pretty, unless you are very lucky (Luck that seems to be reserved to textbook writers. Go figure.).

share|cite|improve this answer

Let's look at that term, $$\sum_{a=n-2}^{\infty}m_2f_az^a$$ Now you know that $f_{n-2}=f_{n-1}=0$, so that's $$\sum_{a=n}^{\infty}m_2f_az^a=m_2\sum_{a=n}^{\infty}f_az^a=m_2(F(z)-z)$$ Well, you can do something like that for each of the terms in your sum. Then all you have to do is solve for $F(z)$.

EDIT: Another way to organize the calculation is to take your first expression for $F(z)$ and multiply both sides of the equation by the "characteristic polynomial" $$1-m_1x-m_2x^2-\cdots-m_nx^n$$ and you'll find the right side collapses down to a polynomial.

share|cite|improve this answer

Your Answer


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.