<s>[INST] Given functions $f,g$ find the direct form for $f(x)=g(x)+f(x-1)$ Let $g(x)=1+x+\frac{x(x+1)}{2}$ and let $f(x)=g(x)+f(x-1)$. Find the closed form for $f(x)$ and $x\geq0$ given that $f(0)=0$.
So what we are asked are is a direct form for $$\sum_{n=1}^{k}g(n)$$
I want to show that $$\sum_{n=0}^{k}g(n)=\frac{1}{2}(\sum_{n=0}^{k+1}n+\sum_{n=0}^{k+1}{n^2})=\dfrac{(k+1)(k+2)(k+3)}{6}$$
edit 1: $f,g$ are defined on the integers.
 [/INST] Use generating functions.
Define $f(-n) = 0$ and say that for all $n \geq 1$ we have $$f(n) = 1+n+\frac{1}{2} n(n+1) + f(n-1)$$
Then $$F(y) := \sum_{n=1}^{\infty} f(n) y^n = \sum_{n=1}^{\infty} [1+n+\frac{1}{2}n(n+1) + f(n-1)] y^n \\
= \sum_{n=1}^{\infty} y^n + \sum_{n=1}^{\infty} n y^n + \sum_{n=1}^{\infty} \frac{n(n+1)}{2} y^n + y \underbrace{\sum_{n=1}^{\infty} f(n-1) y^{n-1}}_{\sum_{n=0}^{\infty} f(n) y^n \ = \ f(0) + F(y)} \\
= y (1-y)^{-1} + y (y-1)^{-2} + y (1-y)^{-3} + y F(y)$$
so $$F(y)(1-y) = y(1-y)^{-1} + y (y-1)^{-2} + y (1-y)^{-3}$$
whereupon $$F(y) = y (1-y)^{-2} + y (1-y)^{-3} + y (1-y)^{-4}$$
Finally, we can just work out the coefficient of $y^n$ in this expression: it's $$f(n) = \frac{1}{6} n (11 + 6 n + n^2)$$
</s>