# Find the sum to n terms

$$S=1^2+3^2+6^2+10^2+15^2+.......$$

My attempt is as follows:

$$T_n=\left(\frac{n\cdot\left(n+1\right))}{2}\right)^2$$

$$T_n=\frac{n^4+n^2+2\cdot n^3}{4}$$

$$S=\frac{1}{4}\cdot\sum_{n=1}^{n}\left(n^4+n^2+2\cdot n^3\right)$$

Now to solve this one has to calculate $$\sum_{n=1}^{n}n^4$$ which will be a very lengthy process, is there any shorter method to solve this question?

By the way I calculated $$\sum_{n=1}^{n}n^4$$ and it came as $$\dfrac{\left(n\right)\cdot\left(n+1\right)\cdot\left(2\cdot n+1\right)\cdot\left(3\cdot n^2+3\cdot n-1\right)}{30}$$, then I substituted this value into the original equation.

Then I got final answer as $$\dfrac{\left(n\right)\cdot\left(n+1\right)\cdot\left(n+2\right)\cdot\left(3\cdot n^2+6\cdot n+1\right)}{60}$$

But it took me a very long time to calculate all of this, is there any shorter way to solve this problem?

• This is A024166 in OEIS. They don't appear to provide a simple closed formula for it.
– lulu
Sep 29, 2019 at 13:42
• actually my requirement is to solve this faster, I did it in the conventional way and it took a lot of time. Sep 29, 2019 at 13:49
• Have you seen this picture proof for $\sum r^4$ ? Sep 29, 2019 at 14:08
• Alternatively, the standard way to do $\sum_rr^k$ is to do $\sum r(r+1)\dots(r+k-1)$ Sep 29, 2019 at 14:11
• Don't have multiple identically-named variables in the same expression! It is very confusing. For example, in the summations, either change the variable denoting the number of terms or change the variable that is being summed over. Sep 29, 2019 at 22:14

It is easier to do this kind of problem using factorial polynomials than conventional polynomials. Using falling factorials, for example, we would use $$(n)_4=n(n-1)(n-2)(n-3)$$ rather than $$n^4$$. The wiki articles explains how to convert from conventional polynomials to falling or rising factorials under in the section titled, "Connection coefficients and identities." The advantage of using factorial polynomials comes in summation. We have, for example $$(n+1)_5-(n)_5=(n+1)n(n-1)(n-2)(n-3)-n(n-1)(n-2)(n-3)(n-4)=5(n)_4$$ so that $$\sum_{n=1}^k(n)_4=\frac15\sum_{n=1}^k((n+1)_5-(n)_5)={(k+1)_5-1\over5}$$

EDIT

In this case, it's very easy, because we have $$T_n=\frac14(n+1)_2(n+1)_2$$ and we can use one of the formulas under the "Connection coefficients and identities" section to get$$T_n=\frac14(n+1)_2(n+1)_2=\sum_{k=0}^2{2\choose k}{2\choose k}(n+1)_{4-k}$$

• Wow...what a nice and simple approach! Sep 29, 2019 at 15:09
• See Concrete Mathematics by Donald Knuth et. al. Jul 13, 2020 at 16:40

Well...there's a way to get a good guess of the answer. You could say to yourself (or plot the data!) that it looks like a 5th degree polynomial, $$p(n) = a_5n^5 + a_4 n^4 + \ldots + a_0.$$ Then you know that $$p(n+1) - p(n)$$ is the thing you've called $$T_n$$, but it's also $$a_5[(n+1)^5 - n^5] + a_4 [(n+1)^4 - n^4] + \ldots + a_1 [(n+1)^1 - n^1]$$ which you can write out as a 4th degree polynomial. The first term will be $$4 a_5 n^4,$$ I think, which I got by simply expanding $$(n+1)^5 - n^5$$ using Pascal's triangle.

Setting this 4th degree poly equation to $$T_n$$, you get a triangular system of equations that can be backsubstituted to get an answer.

OF course, you then must check that the answer is in fact correct. You know it satisfies the recurrence, but you also need to show it gives the correct values for the first few values of $$n$$ (perhaps the first six?)

Is it faster? Probably. But not a lot. And if the answer had turned out not to be polynomial, you'd have wasted a lot of time.

You can use this result: why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

Since $$T_n$$ is of degree $$4$$ then its sum will be of degree $$5$$.

So let $$S(n)=a_0+a_1n+a_2n^2+a_3n^3+a_4n^4+a_5n^5$$.

Then you can proceed by solving the system obtained calculating the first $$6$$ terms $$S(1)$$ to $$S(6)$$.

• yeah this is the good way, actually we don't need $a_0$, S(n) will always a multiple of n Sep 29, 2019 at 14:15
• you can even simplify it further using Saulspatz hint. If you write $S(n)=a_0+a_1(n-1)+a_2(n-1)(n-2)+\cdots+a_5(n-1)(n-2)(n-3)(n-4)(n-5)$ then the system is even easier to solve since it is triangular.
– zwim
Sep 29, 2019 at 14:17

You may use the hockey-stick identity, like in the computation of $$\sum_{n=1}^{N}n^m$$. We have

$$\binom{n}{2}^2 = 6\binom{n}{4}+12\binom{n}{3}+7\binom{n}{2}+\binom{n}{1}$$ hence $$\begin{eqnarray*} \sum_{n=1}^{N}\binom{n}{2}^2 &=& 6\binom{N+1}{5}+12\binom{N+1}{4}+7\binom{N+1}{3}+\binom{N+1}{2}\\&=&\color{red}{\frac{N(N+1)(N+2)(3N^2+6N+1)}{60}}.\end{eqnarray*}$$

I change a little the notations from your original wording.

$$T(n)=\dfrac{n(n+1)}{2}$$

$$S(n)=\sum\limits_{k=1}^nT(k)^2$$

Cheating on the resulting formula for $$f(n)=\dfrac{n(n+1)(n+2)(3n^2+6n+1)}{60}$$

we notice that $$f(0)=f(-1)=f(-2)=0$$.

Is there a way to exploit these negative indices in order to find the $$(3n^2+6n+1)$$ part more easily?

In fact there is, $$T(n)$$ is perfectly defined for negative numbers so this part does not pose any issue.

But how to interpret $$S(-n)$$?

To be consistent with the summation identity $$\sum\limits_a^{b-1}+\sum\limits_b^c=\sum\limits_a^c$$ when $$a one need to set $$\ \sum\limits_M^m=-\sum\limits_{m+1}^{M-1}$$ for the case $$m.

This results in $$\displaystyle S(-n)=\sum\limits_{k=1}^{-n}T(k)^2=-\sum\limits_{k=-(n-1)}^0T(k)^2$$

I let you do the calculation to verify that $$\begin{array}{lcr}S(0)&=&0\\S(-1)&=&0\\ S(-2)&=&0\\ S(-3)&=&-1\\S(-4)&=&-10\\S(-5)&=&-46\end{array}$$

Now by applying the identification method (I describe in my other post) to $$S(n)=a_0+a_1\,n+a_2\,n(n+1)+a_3\,n(n+1)(n+2)+\cdots+a_5\,n(n+1)(n+2)(n+3)(n+4)$$

You immediately get $$a_0=a_1=a_2=0$$

The others coefficients give you $$S(n)=n(n+1)(n+2)\bigg[\frac 16-\frac 14(n+3)+\frac 1{20}(n+3)(n+4)\bigg]=n(n+1)(n+2)\left(\dfrac{3n^2+6n+1}{60}\right)$$

Once you’ve rewritten your sum as $$\frac14\sum_{k=1}^n k^4+2k^3+k^2$$ it’s not terribly difficult to compute this using generating functions if you use some key tools for manipulating them. To wit, if $$g(x)$$ is the ordinary generating function for the sequence $$\{a_n\}_{n=0}^\infty$$, then $$g(x)/(1-x)$$ is the o.g.f. for the sequence of partial sums $$\{\sum_{k=0}^na_k\}_{n=0}^\infty$$, and similarly, $$x\frac d{dx}g(x)$$ is the o.g.f. for $$\{na_n\}_{n=0}^\infty$$. So, starting with the o.g.f. $$(1-x)^{-1}$$ for the sequence of all ones, we have $$\left\{\sum_{k=0}^n k^2\right\}_{n=0}^\infty \stackrel{ogf}{\longleftrightarrow} \frac1{1-x}\left(x\frac d{dx}\right)^2\frac1{1-x} = {x+x^2 \over (1-x)^4},$$ therefore $$\sum_{k=0}^n k^2 = [x^n]{x+x^2\over(1-x)^4} = [x^{n-1}]\frac1{(1-x)^4} + [x^{n-2}]\frac1{(1-x)^4},$$ which you can compute using the generalized binomial theorem. Similarly, $$\sum_{k=0}^n k^3 = [x^n]{x+4x^2+x^3\over(1-x)^5} \\ \sum_{k=0}^n k^4 = [x^n]{x+11x^2+11x^3+x^4\over(1-x)^6}.$$