2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is A024166 in OEIS. They don't appear to provide a simple closed formula for it. $\endgroup$ – lulu Sep 29 '19 at 13:42
  • $\begingroup$ actually my requirement is to solve this faster, I did it in the conventional way and it took a lot of time. $\endgroup$ – user3290550 Sep 29 '19 at 13:49
  • $\begingroup$ Have you seen this picture proof for $\sum r^4$ ? $\endgroup$ – almagest Sep 29 '19 at 14:08
  • $\begingroup$ Alternatively, the standard way to do $\sum_rr^k$ is to do $\sum r(r+1)\dots(r+k-1)$ $\endgroup$ – almagest Sep 29 '19 at 14:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Solomon Ucko Sep 29 '19 at 22:14
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow...what a nice and simple approach! $\endgroup$ – John Hughes Sep 29 '19 at 15:09
  • $\begingroup$ See Concrete Mathematics by Donald Knuth et. al. $\endgroup$ – Felix Marin Jul 13 at 16:40
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yeah this is the good way, actually we don't need $a_0$, S(n) will always a multiple of n $\endgroup$ – user3290550 Sep 29 '19 at 14:15
  • $\begingroup$ 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. $\endgroup$ – zwim Sep 29 '19 at 14:17
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.