Finding sum of none arithmetic series

I have a question to find the sum of the following sum: $$S = \small{1*1+2*3+3*5+4*7+...+100*199}$$ I figured out that for each element in this series the following holds: $$a_n = a_{n-1} + 4n - 3$$ But I don't know where to go from here, I tried subtracting some other series but that did not work very well

Each term in the equation is $$n(2n-1)$$, so $$S=\sum_{n=1}^{100}{n(2n-1)}=2\sum_{n=1}^{100} n^2-\sum_{n=1}^{100} n=2\frac{m(m+1)(2m+1)}{6}-\frac{m(m+1)}{2}$$ where $$m=100$$.

By the telescoping sum we obtain: $$\sum_{n=1}^{100}n(2n-1)=\sum_{n=1}^{100}\left(\frac{n(n+1)(4n-1)}{6}-\frac{(n-1)n(4n-5)}{6}\right)=$$ $$=\frac{100\cdot101\cdot399}{6}=671650.$$

• Those two expressions whose difference is the term to be added seems like a magic trick. How did you (and how could someone else) come up with those expressions? – Rory Daulton Jan 26 at 22:04
• @Rory Daulton We know that the sum is divided by $n(n+1)$ and it's third degree. Thus, for we can write $\sum\limits_{k=1}^n(n(n+1)(a(n+1)+b)-(n-1)n(an+b))$ and to find values of $a$ and $b$. – Michael Rozenberg Jan 26 at 22:36

This is, for $$n=100$$, $$s(n) =\sum_{k=1}^n k(2k-1) =\sum_{k=1}^n (2k^2-k) =2\sum_{k=1}^n k^2 -\sum_{k=1}^n k$$.

Plug in the formulas for the sums and you are done.

$$a_n=\sum_{r=1}^n(4r-3)+a_0=\dfrac n2(1+4n-3)+a_0=2n^2-n+a_0$$

$$\sum_{n=1}^ma_n=2\sum_{n=1}^mn^2-\sum_{n=1}^mn+a_0\sum_{n=1}^m1$$

Here $$a_0=0$$

Alternatively,

$$a_m=b_m+a+bm+cm^2$$

$$4n-3=a_n-a_{n-1}=b_n-b_{n-1}+b+c(2n-1)=b_n-b_{n-1}+2c(n)+b-c$$

WLOG set $$2c=4,b-c=-3\iff c=b+3$$ to find $$b_n=b_{n-1}$$

set $$a=0$$ so that $$b_m=a_m=0$$

Via generating functions we first find the generating function for each term and then sum them up. I'll build from the ground up. It may look overcomplicated but it also doesn't require remembering too many special identities. Our goal is to find $$S_{99}$$ where

\begin{align*} S_m = \sum_{n=0}^{m} a_n \end{align*}

where

\begin{align*} a_0 &= 1 \\ a_n &= (n + 1)(2n + 1) \\ &= a_{n-1} + 4n + 1 \end{align*}

Now to find the generating function for our $$a_n$$ we find

\begin{align*} A(x) &= \sum_{n=0}^{\infty} a_n x^n \\ A(x) - a(0) &= \sum_{n=1}^{\infty} (a_{n-1} + 4n + 1) x^n \\ A(x) - 1 &= \sum_{n=1}^{\infty} a_{n-1}x^n + \sum_{n=1}^{\infty} (4n +1) x^n \\ A(x) - 1 &= x\sum_{n=0}^{\infty} a_{n}x^n + (\sum_{n=0}^{\infty} (4n +1) x^n) - (4*0 + 1) \\ A(x) &= xA(x) + (4\frac{x}{(x - 1)^2} + \frac{1}{x-1}) \\ (1 - x)A(x) &= \frac{4x + (1 - x)}{(1 - x)^2} \\ A(x) &= \frac{3x + 1}{(1 - x)^3} \end{align*}

Summing them all up is easy enough, since $$S_0 = 0$$:

\begin{align*} S(x) &= \sum_{n=0}^{\infty} S_n x^n \\ S(x) - S(0) &= \sum_{n=1}^{\infty} (S_{n - 1} + [y^n]A(y)) x^n \\ (1 - x)S(x) &= A(x) \\ S(x) &= \frac{3x + 1}{(1 - x)^4} \end{align*}

Now we want to find the coefficient for $$S(x)$$ \begin{align*} [x^n]S(x) &= [x^n]\frac{3x + 1}{(1 - x)^4} \\ &= [x^n]\left(3x + 1\right) \sum_{n=0}^{\infty}\binom{n + 3}{3}x^n \tag{1} \\ &= \left(3[x^{n-1}] + [x^n]\right) \sum_{n=0}^{\infty}\binom{n + 3}{3}x^n \tag{2}\\ &= 3\binom{n+2}{3} + \binom{n+3}{3}\\ &= \frac{1}{2}(n+2)(n+1)n + \frac{1}{6}(n+3)(n+2)(n+1) \end{align*}

• In (1) we use the binomial series representation

• In (2) we use the linearity of the coefficient of operator and $$[x^n]x^kS(x)=[x^{n-k}]S(x)$$.

Finally, plugging in $$n = 99$$: $$\frac{1}{2}*101*100*99 + \frac{1}{6}*102*101*100 = 671 650$$

Without using any actual intelligence, you can guess that since the terms are roughly quadratic, the sum should be roughly cubic, so you guess that it is a third degree polynomial $$an^3 + bn^2 + cn + d$$. Then you plug in the values for n = 0, 1, 2, and 3, get for linear equations with four unknowns, and solve to get a, b, c and d.

Try n = 4, 5, 6 to make sure this actually worked, and then it would be easy to prove by induction.