finding a closed formula for $\sum_{k=0}^{n} k{2n \choose k}$

Question

my attempt:

$\sum_{k=0}^{n} k{2n \choose k}=\sum_{k=0}^{2n} k{2n \choose k}-\sum_{k=n+1}^{2n} k{2n \choose k}$

the first term in the right hand side

suppose there are $2n$ poeple, we have to choose a community from them ,and then we have to choose a president from the community chosen ,so if we choose 1 people then there is one possiblity for choose the president ,and if we choose 2 people then there are two possibility for choose the president,and so on,so all ways possible is $\sum_{k=0}^{2n} k{2n \choose k}$,and we can do it by an other way; we can choose $1$ person from them and then we have to choose a community from the remaining $2n-1$;the numbers of ways to do it,is;${2n \choose 1} 2^{2n-1}$

the second term in the right hand side

suppose there are $2n$ poeple, we have to choose a community from them but thier members doesnot less than $n+1$ people ,and then we have to choose a president from the community chosen ,so if we choose $n+1$ people then there is $n+1$ possiblity for choose the president,and so on,so all ways possible is $\sum_{k=n+1}^{2n} k{2n \choose k}$and we can do it by an other way;we can choose $n+1$ people from $2n$ and,and choose a president from those $n+1$ people then we have to choose a community from the remaining ,that's means;$(n+1){2n \choose n+1} 2^{2n-(n-1)}=(n+1){2n \choose n+1} 2^{n-1}$

so finally;$\sum_{k=0}^{n} k{2n \choose k}=\sum_{k=0}^{2n} k{2n \choose k}-\sum_{k=n+1}^{2n} k{2n \choose k}$

$={2n \choose 1} 2^{2n-1}-(n+1){2n \choose n+1} 2^{n-1}$

does my attempt correct?

Answer 1

Combinatorics are not my strong suite, but I believe the issue lies with your second method for choosing a set of more than $n+1$ from $2n$, where you possibly double count.

You first choose $n+1$ people, then choose a president from this set, then choose additional people to add on. But consider the set $\{a,b,c,d,e,f\}$, choosing $\{a,b,c,f\}$ with $a$ as president and $\{a,b,d,f\}$ with $a$ as president are covered as separate cases in the first two choices. But then they are counted as the same choice if the additional people are chosen as $\{d,e\}$ and $\{c,e\}$ respectively.

Unfortunately, I cannot think of a way to mend your argument to finish the proof. Perhaps someone else can figure something out?

Answer 2

@person has found the flaw. Let's fix it

In the second scenario, we can choose the president among the $2n$ people, and afterwards choose a set of at least $n$ members from the remainin $2n-1$ . The counting is

$$ 2n \sum_{k=n}^{2n-1} \binom{2n-1}{k}$$

But the sum, is $$ \frac{1}{2} \sum_{k=0}^{2n-1}\binom{2n-1}{k} = 2^{2n-2}$$

(This can also be seen considering that each choosing of at least $n$ members out of $2n-1$ maps one to one to the complementary choosing of less than $n$ members)

Hence the final result is

$$ 2n 2^{2n-1} - 2n 2^{2n-2} = n 2^{2n-1}$$

Answer 3

As mentioned in comments, the argument that you are making for the second term of RHS can directly be made for the LHS.

The LHS is equivalent to first choosing a president from $2n$ people and then choosing $(n-1)$ regular members on the committee from remaining $(2n-1)$ people.

$ \displaystyle \displaystyle \sum_{k=0}^n k \cdot \binom{2n}{k} = 2n \sum_{k=0}^{n-1} \binom{2n-1}{k} = 2n \sum_{k=n}^{2n-1} \binom{2n-1}{k}$

So,

$ \displaystyle \displaystyle \sum_{k=0}^n k \cdot \binom{2n}{k} = n \sum_{k=0}^{2n-1} \binom{2n-1}{k}$

Now for $~ \displaystyle \sum_{k=0}^{2n-1} \binom{2n-1}{k}~$, you can either directly use the known identity from binomial theorem or use a combinatorial proof. The expression is equivalent to choosing members for a committee and number of members can vary from $0$ to $(2n-1)$. That is equivalent to exercising two choices for each of $(2n-1)$ people - either they are in the committee or they are not and that is $2^{2n-1}$.

That leads to answer $~n \cdot 2^{2n-1}$.