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?
 A: 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}$$
A: 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}$$
A: $$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}$$
A: 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}$
A: $$\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$$
