Solve recurrence relation $T(n)=T(n−1)+n^3$

Question

I know that

$$T(1)=1$$

and

$$k=n-1$$

Try to solve:

$$ T(n)=T(n-1)+n^3 \\ = T(n-2)+(n-1)^3 + n^3 \\ = T(n-3)+(n-2)^3+(n-1)^3+n^3 \\ = T(n-k)+\sum_{i=0}^{k-1} (n-i)^3$$

I think the nexst step is to eliminate the sum. But I am not sure how. One idea is to use little gauss:

$$\sum_{i=1}^{k} k=n(n+1)/2$$

but I am not sure how I can apply this to $$(n-i)^3$$

Any ideas?

Answer 1

As $T(n)-T(n-1)$ is a third degree polynomial in $n$, we can infer that $T(n)$ is a fourth degree polynomial.

Hence we compute the first five values

$$T(1)=1,T(2)=9,T(3)=36,T(4)=100,T(5)=225$$

and build the corresponding Lagrange polynomial which is

$$\frac{n^2(n+1)^2}4.$$

---

For ease of computation, you can notice that the values are perfect squares, namely $$1^2,3^2,6^2,10^2,15^2$$ where you recognize triangular numbers.

Answer 2

In the same spirit as Yves Daoust's answer, let $$T_n=a n^4+b n^3+c n^2+d n+e$$ Now developing $$T_n-T_{n-1}-n^3=(-a+b-c+d)+n (4 a-3 b+2 c)+n^2 (3 b-6 a)+(4 a-1) n^3$$ and all coefficients must be zero.

Starting from the right to the left of the rhs, you get $a$, then $b$, then $c$ and finally $d$ and $e$ would be fixed by any initial condition.

Answer 3

There are general formulae for these kinds of sums, but here's one way to derive it.

Notice that: $$1^4 = (0 + 1)^4 = 0^4 + 4*1*0^3 + 6 * 1^2*0^2 + 4 * 1^3 * 0 + 1^4$$ $$2^4 = (1 + 1)^4 = 1^4 + 4*1*1^3 + 6 * 1^2*1^2 + 4 * 1^3 * 1 + 1^4$$ $$...$$ $$n^4 = ((n-1) + 1)^4 = (n-1)^4 + 4*1*(n-1)^3 + 6 * 1^2*(n-1)^2 + 4 * 1^3 * (n-1) + 1^4$$ $$(n+1)^4 = (n + 1)^4 = n^4 + 4*1*n^3 + 6 * 1^2*n^2 + 4 * 1^3 *n + 1^4$$

And let's sum up all these identities, the LHS is the sum of the 4th powers $$1^4 + 2^4+...+(n+1)^4$$ The first column is the sum of 4th powers as well, but starting from zero and ending at $n$ instead of $n+1$. The second column is the 4 times the desired sum and third column is 6 times sum of the squares, fourth column is 4 times sum of arithmetic progression and last column is just $(n+1)$. For simplicity let's define our desired sum to be called $S$. Then $$(n+1)^4 = 4 * S + n * (n+1)(2n+1) + 2*(1 + n) * n + n+1$$ a little bit of simplification $$S = \frac{(n+1)((n+1)^3 - n*(2n+1) -( 2n + 1))}{4} = \frac{(n+1)^2((n+1)^2 -(2n+1))}{4}$$ $$ S = \frac{(n+1)^2(n^2 + 2n+1-2n-1)}{4} = \frac{(n+1)^2n^2}{4}$$