Please help me solve this problem.
Show that:
$$\sum_{k=1}^n k{n \choose 2k+1} = (n-2)2^{n-3}$$
7
-
2$\begingroup$ Show that you have attempted to solve the problem on your own. When we know where you are stuck, we can help you better. $\endgroup$– Math LoverCommented Oct 7, 2020 at 9:39
-
2$\begingroup$ Do you want an algebraic or combinatorial solution ? ... and can you share your attempts ... so we have an idea of level ? $\endgroup$– Donald SplutterwitCommented Oct 7, 2020 at 9:41
-
$\begingroup$ I need combinatorial solution. $\endgroup$– Anjana KCommented Oct 7, 2020 at 9:46
-
1$\begingroup$ There is a really neat combinatorial proof ... Hint: $\text{Odd}+1+\text{Odd}=\text{Odd}$. $\endgroup$– Donald SplutterwitCommented Oct 7, 2020 at 9:47
-
$\begingroup$ Add the tag "combinatorial proof" & tell me if you need more than the hint above. $\endgroup$– Donald SplutterwitCommented Oct 7, 2020 at 9:49
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
Consider $[n]= \{ 1,2, \cdots,n\}$ with their usual order.
Choose an element of $[n]$ excluding the first and last elements. Now choose an odd number of elements before and an odd number of elements after. It easy to see that this enumerates to $(n-2)2^{n-3}$.
Alternatively choose an odd ($ \geq 3$) number of elements from $[n]$ and now choose on of the "even" elements from this subset.
answered Oct 7, 2020 at 9:56
$\begingroup$
$\endgroup$
$$\frac{(1+x)^n-(1-x)^n}{2}=\sum_{k=0}^{n} {n \choose 2k+1} x^{2k+1}$$ $$\frac{(1+x)^n-(1-x)^n}{2x}=\sum_{k=0}^{n} {n \choose 2k+1} x^{2k}$$ Differentiate w.r.t. $x$ both sides $$\frac{n(1+x)^{n-1}+n(1-x)^{n-1}}{2x}+\frac{(1+x)^n-(1-x)^n}{-2x^2}=\sum_{k=0}^{n} 2k {n \choose 2k+1} x^{2k-1}$$ Now put $x=1$ in above, to get $$\sum_{k=0}^{n} k{n \choose 2k+1}=2^{n-3}(n-2)$$
the upper limit of the sum could be $[n/2]$ or $n$.
