The problem is to prove the following statement for all natural numbers. $$f(n)=\sum_{k=0}^n\binom{n+k}{k}\left(\frac{1}{2}\right)^k=2^n$$  I already proved this using mathematical induction. But, my instinct is telling me that there is some kind of combinatorial/algebraic method that can be used to solve this easily. (Unless my instinct is wrong.) Can anyone give me hint on how to do this?
18020
How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $n$?  I tried using the  but I guess I am applying it incorrectly. With the snake oil technique we have $$F(x)= \sum_{n=0}^{\infty}\left\{\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}\right\}x^{n}.$$ I think I have to interchage the summation and do something. But I am not quite comfortable in interchanging the summation. Like after interchaging the summation will $$F(x)=\sum_{k=0}^{n}\sum_{n=0}^{\infty}\binom{n+k}{k}\frac{1}{2^k}x^{n}?$$ Even if I continue with this I am unable to get the correct answer.  How does one prove this using the Snake oil technique?  A combinatorial proof is also welcome, as are other kinds of proofs.
89125
I was assigned the following problem: find the value of $$\sum_{k=1}^{n} k \binom {n} {k}$$ by using the derivative of $(1+x)^n$, but I'm basically clueless. Can anyone give me a hint?
76737
In  I prove, using generating functions, a statement equivalent to  $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even.  (Clearly the sum is $0$ when $n$ is odd.)  The nice expression on the right-hand side indicates that there should be a pretty combinatorial proof of this statement.  The proof should start by associating objects with even parity and objects with odd parity counted by the left-hand side.  The number of leftover (unassociated) objects should have even parity and should "obviously" be $2^n \binom{n}{n/2}$.  I'm having trouble finding such a proof, though.  So, my question is     Can someone produce a combinatorial proof that, for even $n$, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}?$$   Some thoughts so far:   Combinatorial proofs for $\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k}  = 4^n$ are given by  and by .  The proofs are basically equivalent.  In Phira's argument, both sides count the number of paths of length $2n$ starting from $(0,0)$ using steps of $(1,1)$ and $(1,-1)$.  By conditioning on the largest value of $2k$ for which a particular path returns to the horizontal axis at $(2k,0)$ and using the facts that there are $\binom{2k}{k}$ paths from $(0,0)$ to $(2k,0)$ and $\binom{2n-2k}{n-k}$ paths of length $2n-2k$ that start at the horizontal axis but never return to the axis we obtain the left-hand side.  With these interpretations of the central binomial coefficients $2^n \binom{n}{n/2}$ could count (1) paths that do not return to the horizontal axis by the path's halfway point of $(n,0)$, or (2) paths that touch the point $(n,0)$.  But I haven't been able to construct the association that makes these the leftover paths (nor do all of these paths have even parity anyway).  So perhaps there's some other interpretation of $2^n \binom{n}{n/2}$ as the number of leftover paths.    Update. Some more thoughts:  There's another way to view the identity $\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k}  = 4^n$.  Both sides count the number of lattice paths of length $n$ when north, south, east, and west steps are allowed.  The right side is obvious. The left side has a similar interpretation as before: $\binom{2k}{k}$ counts the number of NSEW lattice paths of length $k$ that end on the line $y=0$, and $\binom{2n-2k}{n-k}$ counts the number of NSEW lattice paths of length $n-k$ that never return to the line $y =0$.  So far, this isn't much different as before.  However, $2^n \binom{n}{n/2}$ has an intriguing interpretation: It counts the number of NSEW lattice paths that end on the diagonal $y = x$ (or, equivalently, $y = -x$).  So maybe there's an involution that leaves these as the leftover paths.  (Proofs of all of these claims can be found on , for those who are interested.)
83167
$$2^{n-2} n (n -1) = \sum\limits_{k=2}^n k (k - 1) \binom{n}{k}.$$  I'm completely stumped. I just have no idea how to do this. What I've tried so far has been simplifying the right hand side slightly to $\sum\limits_{k=2}^n \binom{n}{k - 2}$, and then proving that this somehow is equal to some manipulation of the left hand side. I can't seem to find any breakthroughs that way though.  If anyone could help out or point me in the right direction that would be great.  EDIT: I've actually just realized my simplification of the right hand side is wrong. Now I'm even more stuck.
74644
If $l$ and $n$ are any positive integers, is there a  proof of the identity     $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$   which uses the Inclusion-Exclusion Principle?  (If necessary, restrict to the case where $l\ge n$.)    This question is closely related to   and also
53069
I need to proof this following equality :  $$\binom{m+n}{m}=\sum_{i=0}^m \left(\binom{m}{i}\binom{n}{i}\right)$$  This is what I did combinatoric proof:  Left : subset with $m$ members from $m+n$  Right : $\binom{m}{i} \rightarrow$ The number of subsets in set $m$ could also be written as $2^m$ AND $\binom{n}{i} \rightarrow$ the number of subsets with $m$ members from set $n$  In case $ n \leq m \implies \binom{n}{i}=2^n$  So this is what I came up with I still can't see why those expression are equal.  Any ideas? Thanks.
122214
I believe the following is an identity (I've tested with a few random $m$ and $n$ values, could be wrong though):  $$\sum_{k= 0}^{\infty}{m \choose k}{n \choose k}k=n\binom{m+n-1}{m-1}$$ but I'm not sure how to prove it.   Initially I thought of considering the right side combinatorially: pick $m-1$ things from a bucket of $m+n-1$ things and repeat this $n$ times. But how do I think of the left side combinatorially, since there is an infinite sum? Or maybe this is the incorrect approach?
24152
Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
85347
I'm trying to prove the following  $$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (n+2)2^{n-1} $$  using the identity $$ \sum_{r=0}^{n} \binom{n}{r} = 2^{n} $$  but I'm not able to. This is what I did so far,   $$ \sum_{r=0}^{n}(r+1) \binom{n}{r} = (1) \binom{n}{0} + (2) \binom{n}{1} + ... + (n+1) \binom{n}{n} $$
22727
Find a combinatorial argument for the following binomial identity:   $$n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} .$$   Algebraic proofs can be found at  , and a related identity at  .
69136
Give a combinatorial proof of the following identity:  $$3^n=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}$$  I can't see any counting argument that would yield $3^n$, and the right hand side is also pretty opaque. For some reason I really really suck at doing these proofs - I just started my first combinatorics course.
60053
How  can  i  prove  that :  $$\binom{n}{0}^2+\binom{n}{1}^2+\binom{n}{2}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}$$  i tried to prove it : by   $$\binom{2n}{n} = \frac{(2n)!}{n!n!} = \frac{2^n (1\cdot3\cdot5\cdots(2n-1))}{n!}$$  but i can’t  take advantage of it.
90968
Must show:     $\sum_{i=0}^n i{n \choose i} = n2^{n-1}$ using a combinatorial argument. I have tried picking the problem apart by determining that the summation is equal to 1/2 of the size of all subsets of a set of size n times n.  But I am having trouble relating that to what each term of the summation represents.
87923
Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$  The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$.  Any help?
115268
Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$.   Today I wrote calculus exam, I had this problem given.  I have the feeling that I will get $0$ points for my solution, because I did this:   Base Case: $n=1$ $$\sum_{k=1}^{1} \binom 1 1 = 1 =  2^1 -1 .$$  Induction Hypothesis: for all $n \in \mathbb{N}$: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$  Induction Step: $n \rightarrow n+1$ $$\sum_{k=1}^{n+1} \binom {n+1} {k} = \sum_{k=1}^{n} \binom {n+1} {k} + \binom{n+1}{n+1} = 2^{n+1} -1$$  Please show me my mistake because next time is my last chance in this class.
30402
I need hint proving this $$\sum_{k=0}^{n}\binom{2n}{k}k=n2^{2n-1}$$
89447
How to combinatorially prove $$L\left(n,k\right)=\sum_{j=0}^{n}{ n\brack j}{j\brace k}$$ Where $L\left(n,k\right),{ n\brack j},{j\brace k}$ denote , ,  respectively.  One may use the following explicit formula to derive the relation: $${j\brace k}=\frac{1}{k!}\sum_{i=0}^{k}\binom{k}{i}\left(-1\right)^{i}\left(k-i\right)^{j}$$ However, I don't know how to prove such a relation using combinatorics.