Given functions $f,g$ find the direct form for $f(x)=g(x)+f(x-1)$

Question

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.

Answer 1

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

Answer 2

Hint: $\;g(k)=1 + \frac{3}{2} k + \frac{1}{2} k^2\,$, then by direct calculation:

$$ f(n) = \sum_{k=1}^{n}g(k) = \sum_{k=1}^{n} 1 + \frac{3}{2} \sum_{k=1}^{n} k + \frac{1}{2} \sum_{k=1}^{n} k^2 = n + \frac{3}{2} \frac{n(n+1)}{2} + \frac{1}{2}\frac{n(n+1)(2n+1)}{6} = \cdots $$