# How to create a generating function / closed form from this recurrence?

Let $f_n$ = $f_{n-1} + n + 6$ where $f_0 = 0$.

I know $f_n = \frac{n^2+13n}{2}$ but I want to pretend I don't know this. How do I correctly turn this into a generating function / derive the closed form?

-
For this problem there’s really no need for generating functions at all: by inspection $$f_n=\sum_{k=1}^nk+6n=\frac{n(n+1)}2+6n=\frac{n^2+13n}2\;.$$ – Brian M. Scott Mar 13 '13 at 14:56
+1 that is why I posted two answers. In fact it's harder to find the closed form using generating functions. – user58512 Mar 13 '13 at 15:24

$$\begin{array}{rcl} G(x) &=& \sum_{n=1}^\infty f_n x^n \\ &=& \sum_{n=1}^\infty (f_{n-1} + n + 6) x^n \\ &=& \sum_{n=1}^\infty f_{n-1} x^n + \sum_{n=1}^\infty n x^ n + \sum_{n=1}^\infty 6 x^n \\ &=& x G(x) + x \frac{d}{dx}\left(\frac{x}{1-x}\right) + 6 \frac{x}{1-x} \end{array}$$

So $$G(x) = \frac{6x^2 - 7x}{x^3 - 3x^2 + 3x - 1} = 7x + 15x^2 + 24x^3 + 34x^4 + 45x^5 + \cdots$$

-
Can you explain the last step at all, how you get to 7x + ... etc – user54089 Mar 13 '13 at 15:11
@user54089, long division or use the recurrence relation (or both and check they are the same to make sure you didn't make a mistake). – user58512 Mar 13 '13 at 15:23
How do you get from the generating function to the closed form? – robjohn Mar 13 '13 at 16:48
@robjohn, my comment says "+1 that is why I posted two answers. In fact it's harder to find the closed form using generating functions." I recommend against using generating functions to find the closed form. I have shown how to find the closed form directly from the recurrence in another answer. – user58512 Mar 13 '13 at 16:49
@caveman: If you are interested, I have derived the general term from the generating function using the appropriate binomial expansions. – robjohn Mar 13 '13 at 17:23

Let $$F(x)=\sum_{n=0}^{\infty}f_nx^n=f_0+\sum_{n=1}^{\infty}f_nx^n=\sum_{n=1}^{\infty}(f_{n-1}+n+6)x^n=$$

$$=\sum_{n=1}^{\infty}f_{n-1}x^{n}+\sum_{n=1}^{\infty}nx^n+\sum_{n=1}^{\infty}6x^n=$$

$$=x\sum_{n=1}^{\infty}f_{n-1}x^{n-1}+x\sum_{n=1}^{\infty}nx^{n-1}+x\sum_{n=1}^{\infty}6x^{n-1}=$$

$$=xF(x)+x\frac{1}{(1-x)^2}+6x\frac{1}{1-x}$$ Generating function is $$F(x)=\frac{x+6x(1-x)}{(1-x)^3}=\frac{7x-6x^2}{(1-x)^3}$$

-
What is wrong there. Why downvote – Adi Dani Mar 13 '13 at 15:52
because it's exactly the same argument as my answer – user58512 Mar 13 '13 at 15:56
it's a good answer but it's been written already – user58512 Mar 13 '13 at 15:58
my answer is independent and is more explicit then your – Adi Dani Mar 13 '13 at 16:00
Please move this discussion to meta. – Mariano Suárez-Alvarez Mar 13 '13 at 16:33

Here's a way to derive the generating function for $f_n$. Write the recurrence as

$$f_n-f_{n-1}=n+6$$.

The RHS has the following generating function:

$$\sum_{n=1}^{\infty} (n+6) x^n = \frac{x (7-6 x)}{(1-x)^2}$$

Let $f(x)$ be the GF of $f_n$. Then from the above recurrence:

$$f(x) - x f(x) = \sum_{n=0}^{\infty} f_n x^n - \sum_{n=1}^{\infty} f_{n-1} x^n = \frac{x (7-6 x)}{(1-x)^2}$$

because $f_0=0$. Therefore

$$f(x) = \frac{x (7-6 x)}{(1-x)^3}$$

-

$$f_0 = 0,\; f_n = f_{n-1} + n + 6$$

so $$f_{n+1} = \sum_{i=0}^n (i + 6) = T(n) + 6n = \frac{n^2 + 13n}{2}$$

-

In two answers, it is derived that the generating function is \begin{align} \frac{7x-6x^2}{(1-x)^3} &=x\left(\frac1{(1-x)^3}+\frac6{(1-x)^2}\right)\\ &=\sum_{k=0}^\infty(-1)^k\binom{-3}{k}x^{k+1}+6\sum_{k=0}^\infty(-1)^k\binom{-2}{k}x^{k+1}\\ &=\sum_{k=1}^\infty(-1)^{k-1}\left(\binom{-3}{k-1}+6\binom{-2}{k-1}\right)x^k\\ &=\sum_{k=1}^\infty\left(\binom{k+1}{k-1}+6\binom{k}{k-1}\right)x^k\\ &=\sum_{k=1}^\infty\left(\binom{k+1}{2}+6\binom{k}{1}\right)x^k\\ &=\sum_{k=1}^\infty\frac{k^2+13k}{2}x^k\\ \end{align} Therefore, we get the general term is $f_k=\dfrac{k^2+13k}{2}$

-
Nice robjohn.+1 – Adi Dani Mar 13 '13 at 17:27