A special case of Vandermonde’s identity

Waking up this morning, I was somehow reminded of this combinatorial identity that appeared on an exam in a “math problem solving” class I took, which I didn’t actually solve during the test because back then I was an idiot. It was

\displaystyle\binom{2n}{n} = \displaystyle\sum_{k=0}^n \binom{n}{k}^2.

Basically, it’s observing that \binom{n}{k}^2 = \binom{n}{k}\binom{n}{n-k} and then seeing that we have an instance of Vandermonde’s identity. The square is basically a form of obfuscation.

This stuff feels so obvious to me now yet it wasn’t back then. To make this entirely self-contained, I will prove Vandermonde’s identity as well for this specific case.

Continue reading “A special case of Vandermonde’s identity”

Advertisements

A cute find closed form of sum problem

19692339_10155494787829320_1775528957_n

A friend pinged me this on Facebook. I decided to look at it to exercise my technical chops. Well, the value of the denominator is given by the hint. In the sum of the first n triangular numbers, k is summed n+1-k times, and the number of ways to split n+1 items in a line and pick one on each side of the split is the same as the number of ways to select 3 items from n+2, with the middle one representing the split point. Finally do a partial fractions to telescope. You’ll get \frac{1/2}{n} - \frac{1}{n+1} + \frac{1/2}{n+2}.