Show that:   $\binom{n+1}{2} = \binom{n}{2} + n$  I think I am supposed to use the number of Combinations formula:   $ \binom{n}{k} = \frac{n(n-1)(n-2)(n-k+1))}{k(k-1)(k-2)..1)} = \frac{n!}{k!(n-k)!}$  I tried to use the formula on the LHS and got this:  $\frac{(n+1)!}{2(n-1)}$
18019
I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$.  I suppose I could use the counting rules in probability, perhaps combination= ${{n} \choose {r}}=\frac{n!}{r!(n-r!)}$.  I want to see an actual proof behind this equation.  Does anyone have any ideas?
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?
95380
I tried to solve this problem without any success. I really hope that you will know the answer. $f(n,m)$ presents the number of binary strings (empty string included) that include at most n times '1', and at most m times '0'.      Prove: $$f(n,m) = \binom{n+m+2}{n+1}-1$$
75040
Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$.   In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where order is not significant and repetitions are allowed. So you have $n$ people you form $r$ teams and select $r$ captains and select $(n-r)$ players.  The RHS divides up a team into 2 sets?
57035
If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below:  $$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$  What if I want to go the other way around though?  That is, I know I want to have $X$ possible combinations, and I want to find all the various pairs of $n$ and $k$ that will give me that number of combinations.  For example, if the number of combinations I want is $3$, I want a formula/method to find that all the pairs that will result in that number of combinations are $(3,1)$ and $(3,2)$  I know I could test all the possible pairs, but this would be impractical for large numbers.  But perhaps there's no easier way of doing this then the brute force approach?
94359
I found the following formula in a book without any proof:  $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$  I don't know how to prove this at all. Could you show me how to prove this? Or If you have any helpful information, please teach me. I need your help.  Update : I .
44806
I've seen many posts regarding a combinatorial proof of the following question. But for a non-combinatorial proof would the following method work? Also... is this the easiest way to arrive at a proof? It seems to be rather verbose.  Show the formula $k {n\choose k} = n {n-1 \choose k-1}$ is true for all integers $n,k$ with $0\le k \le n$.  My answer:  Observe that  $$\begin{align*} {n\choose k}&amp;= \frac {n}{k} {n-1 \choose k-1}\\ &amp;= \frac {n}{k}\left[ {n-2 \choose k-2} + {n-2 \choose k-1}\right]\\ &amp;= \frac {n}{k}\left[ \frac{(n-2)!}{(k-2)!(n-2-(k-2))!} + \frac {(n-2)!}{(k-1)!(n-2-(k-1))!}\right]\\ &amp;= \frac {n}{k}\left[ \frac{(n-2)!}{(k-2)!(n-k)!} + \frac {(n-2)!}{(k-1)!(n-k-1)!}\right]\\ &amp;= \frac{(n-1)!}{(k-1)!(n-k)!} + \frac {(n-1)!}{(k)!(n-k-1)!}\\ &amp;= \frac{(n-1)!}{(k-1)!(n-1-(k-1))!} + \frac {(n-1)!}{(k)!(n-1-k)!}\\ &amp;={n-1 \choose k-1} + {n-1 \choose k}={n \choose k}. \end{align*}$$
97505
Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$  I have expanded it this far:  $$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$  but then I am stuck from where to go from there.
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.
8115
Prove the combinatorial identity $${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k} .$$   I understand the left side, which is obvious, but I'm struggling to get anywhere on the RHS. I also would appreciate suggestions on how to approach these kind of problems. I was told to use committees and split them up, but even then it's not so intuitive to me.  I've tried substituting small numbers to see where I can go.  Thank you in advance for your time.
53055
Simplify the expression $\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k}{k}$  My attempt: Using the formula $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$  $\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots \binom{n+k-1}{k-1}+\binom{n+k}{k}$  =$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k-1}{k-1}+(\binom{n+k-1}{k}+\binom{n+k-1}{k-1})$  =$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +2\binom{n+k-1}{k-1}+\binom{n+k-1}{k}$  I can again use the same formula for the term $2\binom{n+k-1}{k-1}$, and in the next to step to the term $3\binom{n+k-2}{k-2}$.   But I don't think this way the expression will get simplified.   Any help is appreciated.
12098
From its definition a combination $\binom{n}{k}$, is the number of distinct subsets of size $k$ from a set of $n$ elements.  This is clearly an integer, however I was curious as to why the expression  $$\frac{n!}{k!(n-k)!}$$ always evaluates to an integer.  So far I figured:  $n!$, is clearly divisible by $k!$, and $(n-k)!$, individually, but I could not seem to make the jump to proof that that $n!$ is divisible by their product.
122842
I perfectly understand the permutations formula i.e. if you have $n$ things how many ways can you rearrange it if taken $k$ at a time (or if you have $k$ slots)? So you draw the following tree. And the formula comes out naturally. $$^nP_k = \frac{n!}{(n-k)!}$$  I get that it is including all of the duplicates, too. And to get rid of them we use the combinations formula: $$^nC_k = \frac{n!}{k!(n-k)!}$$ Can somebody explain why we have to divide by the &quot;number of ways to re-arrange the slots&quot; to get rid of the duplicates? I understand that it works and the division is used to scale a number down but I am not getting that &quot;aha moment&quot; of why we do it. Can somebody explain it?
25606
Can someone give me a hint how to evaluate $$ \binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{o(n)},$$ where $o(n)$ is $n$ if $n$ is even and $n-1$ otherwise ?
104791
I would like your help with proving that for every  $0 \leq k \leq n$,      $$\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx  . $$   I tried to integration by parts and to get a pattern or to use the binomial formula somehow, but it didn't go well.  Thanks a lot!
65822
Please feel free to close this is necessary as I didn't see exactly this question (some variations that I tried but didn't seem to apply. Prove: $$\sum_{k=0}^{n}{\binom{n}{k}^2}=\binom{2n}{n}$$ I figured trying to muscle through it by expanding and then multiplying each term by variants of 1 such as $\frac{n^2}{n^2}$ and $\frac{n^2(n-1)^2}{n^2(n-1)^2}$ to get common denominators, but that was NOT the way it seemed as it got ugly pretty quickly.  Then I tried thinking up formulas of the binomial theorem that I could differentiate like other sums of binomial coefficient problems and i couldn't think of one.  Any help here would be great.
18228
Let $X=\{1,2,3,\dots,n\}$ where $n\in N$. Show that the number or $r$ combinations of $X$ which contain no consecutive integers is given by   $\binom{n-r+1}{r}$ where $0\le r\le n-r+1$.  I am unable to think of any possible way to prove it.  Please explain the proof and comment on the technique used to help me with problems in the future.   Thanks in Advance!  Thanks for pointing the typing faults!