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

Question

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?

Answer 1

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

Answer 2

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

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

Answer 4

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

Answer 5

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