2
$\begingroup$

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

  • 0
    In this case, Wolfram Alpha can be of great use.2012-06-11

4 Answers 4

5

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.

4

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.

2

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

  • 0
    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)\,.$2012-06-11
1

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