Generating Function of a Linear Recurrence Relation

Question

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.

Answer 1

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

Answer 2

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.