$$\binom{k}{i}\binom{n}{k}=\binom{n}{i}\binom{n-i}{k-i}$$  This identity could be easily shown using algebraic formula of combination. However, I would like to provide a combinatorial proof.  I considered applying Pascal's equality, but got stuck.  Any advice ?
123711
How do I prove by a combinatorial argument that ${{n}\choose{k}} {{k}\choose{j}} = {{n}\choose{j}} {{n-j}\choose{k-j}}$
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.
22081
I want to prove the following: $$\sum_{k=1}^{n}k\binom{n}{k}=n\cdot2^{n-1}$$ what I did is(use binominal): $$\binom{n}{k}X^k\cdot 1^{n-k} = (X+1)^n$$ $$k\binom{n}{k}X^k\cdot 1^{n-k} = k(X+1)^k-1$$ now I replace $k$ by $n$ and insert $X=1$ , I will get now $n\cdot2^{n-1}$ what you are suggesting? there is another way to do that? thanks!
49298
I'm trying to prove that  \begin{equation} \sum_{k= 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1} \end{equation}  with the Binomial Theorem.  I know that the B.T. states that  \begin{equation} (x + y)^n =  \sum_{k= 0}^{n} \binom{n}{k} x^{n-k}y^{k}  \end{equation}  The proof that I have tried starts with:  \begin{equation} n \cdot 2^{n-1} =  \end{equation}  Actually I am stucked with this step.
9682
My question is:  show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this.  We could either explain combinatorically that we are counting the same thing in 2 different ways, in this sense, we are counting the number of ways to choose $m$ elements from a set with $n+1$ elements.  Or we could try like me to prove it algebraically, both ways are valid...I'd like some help, or a push in the right direction.
58852
has the identity $$S(n+1, k+1) = \sum_i {n \choose i} S(i, k)\;.$$ I can't seem to find a proof for this and was wondering what it entails. Is it a purely combinatoric argument, or an algebraic manipulation of the explicit formula $S(n, k) = \frac{1}{k!} \sum_{i=0}^k (-1)^i {k \choose i}(k-i)^n $ with the known recurrence formula $S(n+1, k+1) = S(n, k) + (k+1)S(n, k+1)? $
116422
How can I prove the identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$?  I have to prove it using lattice paths, it should be related to Catalan numbers  The $n$th Catalan number $C_n$ counts the number of monotonic paths along the edges of a grid with $n\times n$  square cells, which do not pass above the diagonal.  See for example    For example $\frac{1}{k}\binom{2k-2}{k-1}$ is exactly $C_{k-1}$, and the other terms can also be expressed in terms of the Catalan numbers.  The second part of the exercise ask to prove the recurrence formula $C_n=\sum_{k=1}^n C_{k-1}C_{n-k}$ using similar reasoning (i.e. lattice paths). So we can't use this formula to prove the first.  Could you help me please?
72043
Why does the following equality hold? $$n!=\sum_{k=1}^n (-1)^{n-k} \binom{n}{k} k^n$$
9
I am stuck with the identity  $$ F_{2n} = \sum_{k=1}^n \binom{n}{k} F_k, $$  which happens to be formula . I am using induction, but so far without too much result.  $$ \sum_{k=1}^{n+1} \binom{n+1}{k} F_k = \\ F_{n+1} + \sum_{k=1}^n \binom{n+1}{k} F_k = \\ F_{n+1} + \sum_{k=1}^n \binom{n}{k} F_k + \sum_{k=1}^n \binom{n}{k-1}F_k =\\ F_{n+1} + F_{2n} + \sum_{k=1}^n \binom{n}{k-1}F_k, $$   I am stuck with the sum $ \sum_{k=1}^n \binom{n}{k-1}F_k$, because, on the other hand   $$ F_{n+1}+ \sum_{k=1}^n \binom{n}{k-1}F_k = F_{2n+1} $$  Which would conclude the proof. What am I missing?
107166
I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant counting trick we can use to arrive at this identity?
43106
I do as follows  $(1+x)^n= \binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n}x^n$   differentiating in both sides  $n(1+x)^{n-1}= \binom{n}{1}+2\binom{n}{2}x+3\binom{n}{3}x^2...+n\binom{n}{n}x^{n-1}$  then, for $x=1$  $n \cdot2^{n-1} = \sum_{k=1}^{n}k\binom{n}{k}$  From here, I don't know how to proceed, I have tried to multiply both sides for $(1+x)$ to make $n \cdot2^{n}$ but then the summatory changes, I don't know how to prove the equality.
33898
I encountered this particular combinatorial identity :$$\begin{align}&amp;1\dbinom{n-1}{r-1}+2\dbinom{n-2}{r-1}+\cdots+(n+1-r)\dbinom{r-1}{r-1}\\=&amp;\dbinom{n}{r}+\dbinom{n-1}{r}+\cdots+\dbinom{r}{r}\\=&amp; \dbinom{n+1}{r+1}\end{align}$$How does one figure it out?
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?
53752
So I'm trying to do a proof for this problem:  If $\displaystyle{k \le \left\lfloor \frac{n}{2} \right\rfloor}$ then $$\displaystyle{\binom{n}{k-1} &lt; \binom{n}{k}}$$  I can do it algebraically but my professor asked for a combinatorial proof.  How would one does it?
46073
Show by combinatorial arguments that:   $$\sum_{k = 0}^m \binom{m}{k}\binom{n}{r + k} = \binom{m + n}{m + r}$$  Hello ,  I want to prove this argument by double counting method, i kinda have an idea of proving by comb args. but not by double counting... Can someone give any clues or ideas? thanks :)
27227
Consider the identity $$\sum_{k=0}^n (-1)^kk!{n \brace k} = (-1)^n$$ where ${n\brace k}$ is a Stirling number of the second kind. This is slightly reminiscent of the binomial identity $$\sum_{k=0}^n(-1)^k\binom{n}{k} = 0$$ which essentially states that the number of even subsets of a set is equal to the number of odd subsets.   Now there is an easy proof of the binomial identity using symmetric differences to biject between even and odd subsets. I am wondering if there is an analogous combinatorial interpretation for the Stirling numbers. The term $k!{n\brace k}$ counts the number of set partitions of an $n$ element set into $k$ ordered parts. Perhaps there is something relating odd ordered partitions with even ordered partitions?  As an added note, there is a similar identity $$\sum_{k=1}^n(-1)^k(k-1)!{n\brace k}=0$$ A combinatorial interpretation of this one would also be appreciated.
45704
Is there an intuitive way, though I am not sure how to find a conceptual proof either, to establish the following identity: $$\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k} = n^n$$ for all natural numbers.  I am thinking about binomial formula $$\sum_{k=0}^n\binom nk x^{n-k}y^k=(x+y)^n$$ but I'm not sure how to use it.  I find this problem tantalizing because it looks as if there should be some sort of intuitive way so that is why I share it here. I am looking for an answer like  if possible. Can you find one?