Find closed formula $f(n)$ from generating function

Question

I'm asked to find a closed formula for

$f(n)=6f(n-1)-9f(n-2)$ for $n>1$ with $f(0)=-1. f(1)=0$,

using the ordinary generating function $F(X)$.

I found $F(X)=-1/(1-3x)^2$ but from there I don't manage to get a satisfactory formula for $f(n)$. Can anyone give me a hint ?

Thanks

I don't think that formula for $F(X)$ is right, because the first deriviative of $F$ at $X=0$ is not $f(1)=0$. — Thomas Andrews, Mar 27 '14 at 20:01
I'm not sure to understand what you want to show, but the formula is true for n>1 so maybe that's why it doesn't work. — Utilisator227, Mar 27 '14 at 20:05

score 3 · Answer 1 · answered Mar 28 '14 at 02:24

The reason you're not getting the closed form from your generating function is that the generating function is wrong. Let $F(x) = \sum_{n \ge 0} f(n) x^n$, then

$$\begin{align} F(x) &= f(0) + f(1)x + \sum_{n \ge 2} f(n) x^n \\ &= f(0) + f(1)x + \sum_{n \ge 2} (6f(n-1) - 9f(n-2))x^n \\ &= f(0) + f(1)x + 6x\sum_{n \ge 2} f(n-1)x^{n-1} - 9x^2\sum_{n \ge 2}f(n-2)x^{n-2}\\ &= f(0) + f(1)x + 6x\sum_{n \ge 1}f(n)x^n - 9x^2\sum_{n \ge 0}f(n)x^n \\ &= f(0) + f(1)x + 6x(F(x) - f(0)) - 9x^2F(x) \end{align}$$ so with $f(0) = -1$ and $f(1) = 0$, you get $$F(x) = -1 + 6x(F(x) + 1) - 9x^2F(x)$$ $$(1 - 6x + 9x^2)F(x) = -1 + 6x$$ which gives $$F(x) = \frac{-1 + 6x}{1- 6x + 9x^2} = \frac{-1+6x}{(1-3x)^2} = \frac{-1}{(1-3x)^2} + \frac{6x}{(1-3x)^2}$$ so $$f(n) = -(n+1)3^n + 6n3^{n-1} = 3^n (-n - 1 + 2n) = 3^n(n - 1)$$

mookid · Accepted Answer · 2014-03-28T02:26:33.880

1

Hint: $$\frac 1{1-x} = \sum x^n\\ \frac 1{(1-x)^2} = \frac d{dx} \frac 1{1-x}.$$

details:

then taking the term by term derivative: $$ \frac 1{(1-x)^2} = \sum (n+1)x^n;\\ -\frac 1{(1-3x)^2} = -\sum (n+1)3^n x^n. $$

However, this method does not work here.

Let us try hte straightforward method instead: the caracteristic equation is $$ r^2 = 6r - 9\iff r=3. $$ Hence, the general solution has the expression $$ f(n) = (A + Bn)3^n $$ and, plugging the initial conditions we get $$ -1 = A;\\ 0 = (A+B)\times 3;\\ f(n) = (n-1)3^n. $$

edited Mar 28 '14 at 02:26

answered Mar 27 '14 at 20:02

mookid

28,236

Thanks a lot. I guess my generating function is wrong then considering what we find doesn't match the first terms... – Utilisator227 Mar 27 '14 at 20:10
the problem is that this expansion of $f$ is only true near 0. – mookid Mar 27 '14 at 20:12
Is there a way to find a more general formula then ? – Utilisator227 Mar 27 '14 at 20:14
that is what I was doing :) – mookid Mar 27 '14 at 20:16
Thanks for your help. I'm going to work on your answer. – Utilisator227 Mar 27 '14 at 20:20
That should be $f(n)=(A+Bn)3^n$ - $n$ not $r$. $r=3$. And then, in the end $f(n)=(n-1)3^n$, not $(r-1)3^n$. – Thomas Andrews Mar 28 '14 at 02:03
exact. thanks ! {}}{ – mookid Mar 28 '14 at 02:05
Your final expression is still wrong, as Thomas Andrews pointed out: it should be $f(n) = (n-1)3^n$, not $(r-1)3^n$. – ShreevatsaR Mar 28 '14 at 02:25
indeed! thanks both of you, I am getting tired ;) – mookid Mar 28 '14 at 02:27

score -1 · Answer 3 · answered Apr 02 '14 at 02:48

Write the recurrence as: $$ f(n + 2) = 6 f(n + 1) - 9 f(n) \qquad f(0) = - 1, f(1) = 0 $$ Multiply by $z^n$ and sum over $n \ge 0$. Recognize: \begin{align} \sum_{n \ge 0} f(n + 1) z^n &= \frac{F(z) - f(0)}{z} \\ \sum_{n \ge 0} f(n + 2) z^n &= \frac{F(z) - f(0) - f(1) z}{z^2} \end{align} and get: $$ \frac{F(z) + 1}{z^2} = 6 \frac{F(z) + 1}{z} - 9 F(z) $$ Solving for $F(z)$, and splitting into partial fractions: $$ F(z) = \frac{1 - 6 z}{1 - 6 z + 9 z^2} = \frac{1}{(1 - 3 z)^2} - \frac{2}{1 - 3 z} $$ This tells us: $$ f(n) = \binom{-2}{n} (-1)^n 3^n - 2 \cdot 3^n = \left( \binom{n + 1}{1} - 2 \right) \cdot 3^n = \frac{n - 3}{2} \cdot 3^n $$

Find closed formula $f(n)$ from generating function

3 Answers3