What is the closed form sum of the convolution of non-zero squares?

Question

I am trying to do the runtime analysis for a coding problem, and I've found that the total number of operations is equal to:

\begin{equation} \sum_{i=1}^{n} i^2 (n-i)^2 \end{equation}

• Where n is the size of the grid data in the problem.

I found the sequence for this function on OEIS:

1, 8, 34, 104, 259, 560, 1092, 1968 ... (see full sequence here: https://oeis.org/A033455)

How do I find a closed form equation that gives me the nth value of this sequence?

For context this is the coding problem (if you're curious): https://www.geeksforgeeks.org/maximum-size-square-sub-matrix-with-sum-less-than-or-equals-to-k/

And in general, I would appreciate any advice you have on finding closed form equations/functions for sequences on OEIS.

Answer 1

Use formulas for $\sum_{i=1}^ni^{k}$, namely Faulhaber's formulas. Quick look gives $O(n^5)$ as complexity.

Answer 2

Using C614's formulas the full solutions is:

\begin{equation} \frac{n^5-n}{30} \end{equation}