11
$\begingroup$

I want to prove the following identity using induction (not double counting method). Although it is a specific version of Vandermonde's identity and its inductive proof is presented here, but I need a direct inductive proof on this, not the general form.

$$\binom{2n}{n}=\sum\limits_{k=0}^n\binom{n}{k}^2$$

I have tried to simplify $\binom{2n+2}{n+1}$ using Pascal's theorem, but did not get any result. Any help?

$\endgroup$
8
+50
$\begingroup$

Suppose $$ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}\tag{1} $$ then $$ \begin{align} \sum_{k=0}^{n+1}\binom{n+1}{k}^2 &=\sum_{k=0}^{n+1}\left[\binom{n}{k}+\binom{n}{k-1}\right]^2\tag{2a}\\ &=\sum_{k=0}^{n+1}\left[\binom{n}{k}^2+\binom{n}{k-1}^2+2\binom{n}{k}\binom{n}{k-1}\right]\tag{2b}\\ &=\binom{2n}{n}\left(1+1+\frac{2n}{n+1}\right)\tag{2c}\\ &=\binom{2n+2}{n+1}\tag{2d} \end{align} $$ Explanation:
$\text{(2a)}$: Pascal's Triangle identity
$\text{(2b)}$: algebra
$\text{(2c)}$: apply $(1)$ and $(3)$
$\text{(2d)}$: $\binom{2n+2}{n+1}=\frac{4n+2}{n+1}\binom{2n}{n}$


Lemma: $$ \sum_{k=1}^n\binom{n}{k}\binom{n}{k-1}=\frac{n}{n+1}\sum_{k=0}^n\binom{n}{k}^2\tag{3} $$ Proof:

Since $\binom{n}{k-1}=\frac{k}{n-k+1}\binom{n}{k}$, we have $\binom{n}{k}+\binom{n}{k-1}=\frac{n+1}{n-k+1}\binom{n}{k}$. Therefore, $$ \frac{n-k+1}{n+1}\left[\binom{n}{k}+\binom{n}{k-1}\right]\binom{n}{k-1}=\binom{n}{k}\binom{n}{k-1}\tag{3a} $$ Since $\binom{n}{k}=\frac{n-k+1}{k}\binom{n}{k-1}$, we have $\binom{n}{k}+\binom{n}{k-1}=\frac{n+1}{k}\binom{n}{k-1}$. Therefore, $$ \frac{k}{n+1}\left[\binom{n}{k-1}+\binom{n}{k}\right]\binom{n}{k}=\binom{n}{k-1}\binom{n}{k}\tag{3b} $$ Adding $(3a)$ and $(3b)$ and cancelling yields $$ \frac{n-k+1}{n+1}\binom{n}{k-1}^2+\frac{k}{n+1}\binom{n}{k}^2=\binom{n}{k-1}\binom{n}{k}\tag{3c} $$ Summing $(3c)$ over $k$, and substituting $k\mapsto k+1$ in the leftmost sum, gives $$ \frac{n}{n+1}\sum_{k=0}^n\binom{n}{k}^2=\sum_{k=1}^n\binom{n}{k-1}\binom{n}{k}\tag{3d} $$ QED

$\endgroup$
3
$\begingroup$

In general, one can show by induction that $$\frac{d^n}{dt^n} f(t)g(t) = \sum_{k=0}^n \binom{n}{k} \biggl(\frac{d^k}{dt^k}f(t) \biggr) \biggl(\frac{d^{n-k}}{dt^{n-k}}g(t) \biggr). \tag{1} $$ For $0 \le k \le r$ integers, one can see by induction that $$\frac{d^k}{dt^k} t^r = r(r-1)\cdots(r-k+1)t^{r-k} = k!\binom{r}{k}t^{r-k}. $$ So in particular, $$\frac{d^n}{dt^n} t^{2n} = n!\binom{2n}{n}t^n. \tag{2} $$ Applying $(1)$ to $f(t) = g(t) = t^n$ gives \begin{align} \frac{d^n}{dt^n} t^{2n} &= \sum_{k=0}^n \binom{n}{k} \biggl(\frac{d^k}{dt^k}t^{n} \biggr) \biggl(\frac{d^{n-k}}{dt^{n-k}}t^{n} \biggr) \\ &= \sum_{k=0}^n \binom{n}{k} \cdot k!\binom{n}{k}t^{n-k} \cdot (n-k)!\binom{n}{n-k} t^k \\ &= \sum_{k=0}^n n! \binom{n}{k}^2 t^n. \tag{3} \end{align} Comparing $(2)$ and $(3)$ gives the desired result.

$\endgroup$
  • $\begingroup$ Using this idea for other functions can give other interesting results. Putting $f(x) = x^a$ and $g(x) = x^b$ gets you Vandermonde's identity $\binom{a+b}{n} = \sum_k \binom{a}{k} \binom{b}{n-k}$. Putting $f(x) = e^{ax}$ and $g(x) = e^{bx}$ gets you the binomial theorem $(a+b)^n = \sum_k \binom{n}{k} a^k b^{n-k}$. $\endgroup$ – arkeet Oct 1 '16 at 1:25

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.