Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

4 Answers 4

up vote 5 down vote accepted

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:

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

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

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

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

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

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

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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