1
$\begingroup$

It can be shown from some rather tedious expansion (or wolframalpha!) that $$\sum_{r=1}^n \binom {2r}2=\frac 16n(n+1)(4n-1)$$

Is it possible to derive this closed form result easily using summation identities of binomial coefficients, with minimal or no algebraic expansion?

The result can also be expressed as $\displaystyle\binom {n+1}2 \frac {4n-1}3$ and resembles the result for the sum of squares. Not that it would necessarily help.

Note also that $\displaystyle\sum_{r=1}^n \binom r2=\binom {n+1}3$.

$\endgroup$
  • 2
    $\begingroup$ The summation index is $r$, yet there is no term under the sum that depends on $r$. $\endgroup$ – Mark Viola Nov 21 '16 at 18:33
  • 1
    $\begingroup$ Well, you can use that $\binom{2n}{2}=4\binom{n}{2}+\binom{n}{1}$ and use some of the usual identities. You can derive that by a counting argument - you can choose $2$ numbers from $\{1,\dots,2n\}$ by either choosing a pair $2k,2k-1$, or choosing a pair not of this form, which amounts to picking a distinct pair $a,b\in\{1,2,\dots,n\}$ and then picking one of the four pairs $\{2a,2b\},\{2a-1,2b\},\{2a,2b-1\},\{2a-1,2b-1\}$. $\endgroup$ – Thomas Andrews Nov 21 '16 at 18:33
  • 1
    $\begingroup$ That results in $4\binom{n+1}{3}+\binom{n+1}{2}$ $\endgroup$ – Thomas Andrews Nov 21 '16 at 18:38
  • $\begingroup$ @Dr.MV - There is now! Thanks. $\endgroup$ – hypergeometric Nov 22 '16 at 1:26
  • $\begingroup$ @ThomasAndrews - Thanks! That's really neat. How would you derive it algebraically? If you would post your comment as a solution I'd upvote and accept it. $\endgroup$ – hypergeometric Nov 22 '16 at 1:29
1
$\begingroup$

You can write:$$\binom{2n}{2}=4\binom{n}{2}+\binom{n}{1}$$ This can be seen with a counting argument. The set of pairs of distinct elements in $\{1,2,\dots,2n\}$ contains $n$ pairs of the form $\{2k-1,2k\}$. The paiselrs not of this form can be found by selecting a pair of distinct values, $a,b\in\{1,2,\dots,n\}$ and then choosing any of the four pairs of $\{2a,2b\},\{2a-1,2b\},\{2a,2b-1\},$ or $\{2a-1,2b-1\}$.

Numerically, any polynomial of degree $k$ can be written as:

$$a_k\binom{n}{k}+a_{k-1}\binom{n}{k-1}+\cdots +a_0\binom{n}{0}$$

For your example, $$\binom{2n}{2}=n(2n-1)=2n^2-n = 4\frac{n^2-n}{2}+n=4\binom{n}{2}+\binom{n}{1}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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