# Compute close formula for a sum.

Let $k$ be a integer. How can we compute the close formula for $$\sum_{m=0}^{k} (m+1)(m+2)(2m+3)(3m+4)(3m+5)?$$

-
In this case, Wolfram Alpha can be of great use. – Pedro Tamaroff Jun 11 '12 at 21:13

We can expand the polynomial we are summing over to give a degree 5 polynomial in $k$, as follows:

$$(m+1)(m+2)(2m+3)(3m+4)(3m+5)=18m^{5}+135m^{4}+400m^{3}+585m^{2}+422m+120$$

Therefore, we can write the summation as:

$$18\sum_{m=0}^{k}{m^{5}}+135\sum_{m=0}^{k}{m^{4}}+400\sum_{m=0}^{k}{m^{3}}+585\sum_{m=0}^{k}{m^{2}}+422\sum_{m=0}^{k}{m}+120\sum_{m=0}^{k}1$$

We can therefore compute the final answer without much difficulty using standard results:

$$$$\sum_{m=0}^{k}{m^{5}}=\frac{k^{2}(2k^{2}+2k-1)(k+1)^{2}}{12}$$$$

$$$$\sum_{m=0}^{k}{m^{4}=\frac{k(2k+1)(k+1)(3k^{2}+3k-1)}{30}}$$$$

$$$$\sum_{m=0}^{k}{m^{3}}=\frac{k^{2}(k+1)^{2}}{4}$$$$

$$$$\sum_{m=0}^{k}{m^{2}}=\frac{k(k+1)(2k+1)}{6}$$$$

$$$$\sum_{m=0}^{k}{m}=\frac{k(k+1)}2{}$$$$

$$$$\sum_{m=0}^{k}{1}=k+1$$$$

Combining all these, we have the following simplified expression:

$$(k+2)^{2}\left(3k^{4}+24k^{3}+67k^{2}+76k+30\right)$$

Testing for a few simple test cases:

\begin{align}k = 1: 1800 \\ k=2: 11040 \\ k=4: 133560\end{align}

These correspond to what we get if we compute the summation by hand, so this is our final closed form.

-

The summand is a polynomial of degree 5, so the sum will be a polynomial of degree 6 in $k$. You can calculate the sum for the first 7 values of $k$ and interpolate the polynomial.

-

For many problems of this type there are special methods which will work, but if this is a "naturally occurring" problem rather than a homework question, here is a method which will work: Multiply out all the brackets and then use the standard results for $\sum k, \sum k^2$, etc

-
It might be easier to represent $p(m)=(m+1)(m+2)(2m+3)(3m+4)(3m+5)$ as a linear combination of $p_i(m)={m\choose i}$ for $0\le i\le 5$ since $$\sum_{m=0}^kp_i(m)={k+1\choose i+1}=p_{i+1}(k+1)\,.$$ – bgins Jun 11 '12 at 21:19

Lemma Supposing that $P(x)$ is a polynomial such that $\deg{}P\le{}n$, we have $P(x) = \sum_{k=0}^n \binom{x}k \Delta^kP(0)$ where $\Delta{}f(x) = f(x+1) - f(x)$ and $\Delta^mf(x) = \Delta\left(\Delta^{m-1}f(x)\right)$.

Lemma's proof First it's easy to show that $\Delta^mf(0)=0$ for $m=0,1,\ldots,\deg{}f$ implies that $f(x)=0$ (Hint: induction on $\deg{}f$). Next, let $f(x)=P(x)-\sum_{k=0}^n\binom{x}k\Delta^kP(0)$, we have $\Delta^mf(x)=\Delta^mP(x)-\sum_{k=0}^n\binom{x}{k-m}\Delta^kP(0)$, and let $x=0$, we have $\Delta^mf(x)=0$, whenever $0\le{}m\le{}n$. Q.E.D.

In your problem, let $P(x) = (x+1)(x+2)(2x+3)(3x+4)(3x+5)$, we have $\sum_{k=0}^5 \binom{x}k \Delta^kP(x)$. How to calculate $\Delta^kP(x)$? Well, suppose $P(k) = a_k$, we have $\begin{array}{|l|l|l|l|l|l|l|} \hline \\ m&\Delta^mP(0)&\Delta^mP(1)&\Delta^mP(2)&\Delta^mP(3)&\Delta^mP(4)&\Delta^mP(5)\\ \hline \\ 0&a_0&a_1&a_2&a_3&a_4&a_5\\ \hline \\ 1&a_1-a_0&a_2-a_1&a_3-a_2&a_4-a_3&a_5-a_4\\ \hline \\ 2&a_2-2a_1+a_0&a_3-2a_2+a_1&a_4-2a_3+a_2&a_5-2a_4+a_3 \\ \hline \end{array}$ and so on. We can make such table to calculate it.

Finally, $\sum_{j=0}^n \sum_{k=0}^5 \binom{x}k \Delta^kP(0) = \sum_{j=0}^n \sum_{k=0}^5 \binom{x}{k+1} \Delta^kP(0)$.

-