Find a good candidate for a closed-form solution of this recurrence relation: $P(n-1)+n^2$.

Question

I want to find a candidate for this recurrence relation:

$$ P(n) = \left\{\begin{aligned} &1 &&: n = 0\\ &P(n-1)+n^2 &&: n>0 \end{aligned} \right.$$

Starting from 0 the first 8 values are 1,2,6,15,31,56,92,141.

I can't figure out a formula for this.

Answer 1

The first few values are 1,2,6,15,31....
The General Term is$${n*(n+1)*(2n+1)\over6}+1$$ Which is the Sum of Squares of first $n$ natural numbers + 1.

Answer 2

Write $P(n) - P(n-1) = n^2 = 2{n \choose 2} + {n\choose 1}$. But ${n \choose 2} = {{n+1} \choose 3}-{n \choose 3}$, and ${n\choose 1} = {{n+1} \choose 2} - {n\choose 2}$, so we have $P(n) - P(n-1) = Q(n) - Q(n-1)$, where $Q(n) = 2{{n+1} \choose 3} + {{n+1} \choose 2} $. Since $P(0) = 1$ and $Q(0) = 0$, we can now conclude that $P(n) = Q(n) +1 = 2{{n+1} \choose 3} + {{n+1} \choose 2} + 1$.

Unfortunately, there is not a very nice closed form for this. But here's the best I can do (the first term here is the sum of the first $n$ squares, a fairly well-known quantity): $\frac{(n-\frac{1}{2})\cdot n\cdot (n+\frac{1}{2})}{3} + 1$