Prove the identity $\sum_{k=2}^{n} k(k-1)\binom{n}{k} =\binom{n}{2} 2^{n-1}$ for all $n=2,3,4,...$
Problem
Source:
Tags: combinatorics
16.07.2017 15:57
$\sum_{k=2}^{n} k(k-1)\binom{n}{k} =\sum_{k=2}^{n} \frac{n!}{(k-2)!(n-k)!}=n(n-1) \sum_{k=2}^{n} \frac{(n-2)!}{(k-2)!(n-k)!}=n(n-1) \sum_{k=2}^{n} \binom{n-2}{k-2}=n(n-1) \sum_{k=0}^{n} \binom{n}{k}=n(n-1)2^n = \binom{n}{2} 2^{n-1}$
22.07.2018 12:17
The following identity also holds: \[ \sum_{k=0}^{n} {\binom{n}{k} \binom{k}{m}} = \binom{n}{m} \cdot 2^{n-m} \]
22.07.2018 12:33
I give a combinatorial proof of \[ \sum_{k=0}^{n} {\binom{n}{k} \binom{k}{m}} = \binom{n}{m} \cdot 2^{n-m} \]Consider the following question: "There are $n$ balls arranged on a line. How many ways are there to color each of them yellow, blue or violet, such that exactly $m$ of them are colored yellow?" LHS One way to do this is to find the number of ways to color exactly $n-k$ violet, $k-m$ blue and $m$ yellow, as $k$ is an integer which ranges from $m$ to $n$. First, color all the balls violet. Next, choose $k$ objects and color them blue. There are $\binom{n}{k}$ ways to do this. Now, from the $k$ balls, choose $m$ of them and color them yellow. There are $\binom{k}{m}$ ways to do this. After we have done this, we now have exactly $n-k$ violet balls, $k-m$ blue balls and $m$ yellow balls. Since $k$ is an integer which ranges from $m$ to $n$, then the number of ways is: $\sum_{k=m}^n\binom{n}{k}\binom{k}{m}=\sum_{k=0}^n\binom{n}{k}\binom{k}{m}$. RHS We first choose the $m$ balls to color yellow. This has $\binom{n}{m}$ ways. Next, to color the rest of the $n-m$ balls, they can either be blue or violet. This has $2^{n-m}$ ways. Hence, the number of ways to do this is $\binom{n}{m}\cdot2^{n-m}$. Therefore, \[ \sum_{k=0}^{n} {\binom{n}{k} \binom{k}{m}} = \binom{n}{m} \cdot 2^{n-m} \]
22.07.2018 14:22
MYL wrote: The following identity also holds: \[ \sum_{k=0}^{n} {\binom{n}{k} \binom{k}{m}} = \binom{n}{m} \cdot 2^{n-m} \] One can differentiate the identity $ \sum_{k=0}^n \binom{n}{k}x^m=(1+x)^n$ $m$ times, and multiply $m!$, to get $$ \sum_{k=0}^{n} {\binom{n}{k} \binom{k}{m}} x^m= \binom{n}{m} \cdot (1+x)^{n-m}$$. Plugging $x=1$ to the equation gives the identity.
15.11.2020 18:23
We can easily prove it by by double differentiating the given equation
11.09.2022 03:52
RagvaloD wrote: $\sum_{k=2}^{n} k(k-1)\binom{n}{k} =\sum_{k=2}^{n} \frac{n!}{(k-2)!(n-k)!}=n(n-1) \sum_{k=2}^{n} \frac{(n-2)!}{(k-2)!(n-k)!}=n(n-1) \sum_{k=2}^{n} \binom{n-2}{k-2}=n(n-1) \sum_{k=0}^{n} \binom{n}{k}=n(n-1)2^n = \binom{n}{2} 2^{n-1}$ In the last step.... shouldn't it be ( n choose 2)*2^(n+1)??? Bec n(n-1)= (n choose 2)*2 and thus n(n-1)*2^n = (n choose 2)*2^(n+1)