3

Given the recursive equation :

$$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$

A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get :

$$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$

Now subtracting both equations :

$$F_n+F_{n-1}+⋯+F_0 - (F_{n-1}+F_{n-2}+⋯+F_0) = 3^n - 3^{n-1} $$

$$ F_n = 3^n - 3^{n-1}$$

But how can I do that using generating functions ? any hints ?

Thanks

user1176409
  • 1
JAN
  • 2,379

1 Answers1

1

Define $f(z):=\sum F_n z^n$ and $g(z):=\sum z^n=\frac{1}{1-z}$. You can see $\sum_{k=0}^{n}F_k$ is the coefficient of $f(z)g(z)$ in the $n$-th term. So we get $$f(z)g(z)=\sum_{k=0}^{\infty}3^nz^n.$$ From this we get $f(z)=\frac{1-z}{1-3z}=\frac{1}{3}+\frac{2}{3}\frac{1}{1-3z}=1+\sum_{k=1}^{\infty}\frac{2}{3}3^kz^k$. The coefficient of this is your $F_n$.

The way to think about these two functions $f$ and $g$ is to write $$\sum_{k=0}^{n}F_k$$ as $$\sum_{k=0}^{n}F_{k}G_{n-k},$$which is a coefficient in a product of two series. In this case we need $G_k=1$. That is why the two functions should be the $f$ and $g$ above.

So, yes, you multiply both sides by $z^n$ (or $z^{-n}$, or sometimes $z^n/n!$, or $z^n/n$; which generating functions are going to be useful depends on the recurrence) summed over all $n$. On both sides you get some series. The trick is to write them in terms of known functions and $f(z)$. There are some known operations on series that have easy translations into operations on the function. See here.

There is also this very good, and free(!) book.

J.G.
  • 115,835
OR.
  • 5,941
  • I kinda lost you ,did you mean to multiply $((F_n+F_{n-1}+⋯+F_0 ))\cdot z^n=3^n z^n$ ? – JAN Jul 20 '13 at 15:43
  • I never really used Generating functions with recursions before , that's why I asked in the first place . If you could add some more explanations regarding the generating functions solution , it would be greatly appreciated . – JAN Jul 20 '13 at 15:52