2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Mar 27 '14 at 20:01
  • $\begingroup$ 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. $\endgroup$ – Utilisator227 Mar 27 '14 at 20:05
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot. I guess my generating function is wrong then considering what we find doesn't match the first terms... $\endgroup$ – Utilisator227 Mar 27 '14 at 20:10
  • $\begingroup$ the problem is that this expansion of $f$ is only true near 0. $\endgroup$ – mookid Mar 27 '14 at 20:12
  • $\begingroup$ Is there a way to find a more general formula then ? $\endgroup$ – Utilisator227 Mar 27 '14 at 20:14
  • $\begingroup$ that is what I was doing :) $\endgroup$ – mookid Mar 27 '14 at 20:16
  • $\begingroup$ Thanks for your help. I'm going to work on your answer. $\endgroup$ – Utilisator227 Mar 27 '14 at 20:20
1
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.