Find the sum to n terms

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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*}$$

Answer 5

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<b<c\ $ one need to set $\ \sum\limits_M^m=-\sum\limits_{m+1}^{M-1}$ for the case $m<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)$$

Answer 6

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}.$$