Why is $\sum_{r=1}^{m-1} (2r+1)r=\sum_{r=1}^{m-1} 4\binom{r}{2} + 3\binom{r}{1}$?

71 Views Asked by At
  • How did the summation expression get transformed to combination?
  • From where did the constants $4$ and $3$ come from?

$$ \begin{align*} T(m^2-1) &= \sum_{r=1}^{m-1} (2r+1)r\\ &= \ \sum_{r=1}^{m-1} 4\binom{r}{2} + 3\binom{r}{1} \\ &= 4\binom{m}{3} + 3\binom{m}{2}. \end{align*} $$

4

There are 4 best solutions below

0
On BEST ANSWER

This is a consequence of the fact that the binomial coefficients form a basis for the space of polynomials; see http://en.wikipedia.org/wiki/Binomial_coefficient#Binomial_coefficients_as_a_basis_for_the_space_of_polynomials .

In this case in particular, the easiest way to derive the result is likely going coefficient by coefficient. In general, ${r\choose k}$ is a polynomial of degree $k$ in $r$; since $(2r+1)r=2r^2+r$ is of degree 2, we should start with ${r\choose 2}$. A quick look at coefficients shows that ${r\choose 2}=\frac12r^2-\frac12r$, so $4{r\choose 2}=2r^2-2r$ and $(2r+1)r=4{r\choose 2}+3r$. But ${r\choose 1}$ is just $r$, so we end up with $(2r+1)r=4{r\choose 2}+3{r\choose 1}$.

The point behind making this change of basis, incidentally, is the next step in evaluating the sum: for any $k$ we have $\sum_{r=0}^{m-1}{r\choose k}={m\choose k+1}$, so once the terms of the original sum have been transformed into binomial form, we can 'collapse' the sums of binomial coefficients into a single binomial coefficient each.

0
On

Do you know $\sum_{r=1}^n r^2=\dfrac{n(n+1)(2n+1)}6$

and $\sum_{r=1}^n r=\dfrac{n(n+1)}2$

also for integer $n,r\ge0,$

$$\binom nr=\frac{n(n-1)\cdots(n-r+1)}{r!}$$

consequently, $\binom n2=\dfrac{n(n-1)}2$ and $\binom n1=n$

0
On

$(2r+1)r = 2(r-1)r + 3r = 4\binom{r}{2} + 3\binom{r}{1}$

2
On

$$\begin{align}\binom r1 =r\qquad &\Rightarrow r=\binom r1\\ \binom r2=\frac {r(r-1)}2\qquad &\Rightarrow r^2=2\binom r2+\binom r1 \end{align}$$ Hence $$\begin{align} \sum_{r=1}^{m-1}(2r+1)r&=\sum_{r=1}^{m-1}2\left[2\binom r2+\binom r1\right]+\binom r1\\ &=\sum_{r=1}^{m-1}4\binom r2+ 3\binom r1\qquad \blacksquare \\ &=4\binom m{3}+3\binom m2 \end{align}$$

NB -

  1. transforming the summand into combinatorial format (or binomial coefficients) makes it easier to sum as you can use the identity $$\sum_{r=0}^{m}\binom ra=\sum_{r=1}^{m}\binom ra=\binom {m+1}{a+1}$$

  2. if you require a numerical value for the final result, it will be faster to calculate it using the combinatorial format