Prove that $$\sum_{k = 0}^n k\binom nk^2 = n \binom{2n-1}{n-1}$$  I have to prove it in a combinatorically. No induction or algebra.
123944
[Corrected question]  I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, or an algebraic solution.
110410
Prove that for any $0\lt r\lt n$ we have $$\binom nr=\binom{n-1}{r-1}+\binom{n-1}r.$$  How do prove this and what step do i take in order for it to be true?
10614
Show that $$\sum_{k=0}^n(-1)^k\binom nk=0$$ So for odd $n$ we have an even number of terms. So $\binom nk=\binom n{n-k}$ which have opposite signs. Thus the sum is 0.  For even $n$ we have that $$\sum_{k=0}^n(-1)^k\binom nk= \binom n0+\sum_{k=1}^{n-1}(-1)^k\binom nk+\binom nn$$ Now $$\sum_{k=1}^{n-1}(-1)^k\binom nk= \sum_{k=1}^{n-1}(-1)^k\left[\binom{n-1}k+\binom{n-1}{k-1}\right]$$ What would that sum be in the square brackets?
38780
So I see this identity a lot but I can't find a detailed combinatorial proof for it.  $$n(n+1)...(n+k-1)=\sum_{j=0}^k \begin{bmatrix}k \\j \end{bmatrix}n^j$$ Can someone please help?
104982
Prove the identity  $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=0$$  Use a combinatorial interpretation of the positive and negative terms.   Edit: I have already proven it using the binomial theorem, more specifically with $(1-1)^n$. I'm having difficulty understanding what is meant by a combinatorial interpretation of the positive and negative terms.    I'm having trouble understanding exactly what is necessary for a combinatorial interpretation. Looking at small cases, I see that the symmetry of the expansion allows us to cancel out lots of terms.   Is this what is meant by a combinatorial interpretation? Is there any resources that introduce the idea of what constitute a combinatorial interpretation?  I feel like the professor threw us off in the deep end and I'm trying to keep my head above water with the few problems I have to work with and that I understand.
100935
The question is - Let $k \geq 1$ be an integer and consider a sequence $n_1,n_2,\cdots,n_k$ of positive integers. Use a combinatorial proof to show that  $\binom{n_1}{2} + \binom{n_2}{2} +\cdots+ \binom{n_k}{2} \leq \binom{n_1+n_2+\cdots+n_k}{2}$  How can i prove this without using induction?  Additionally, For each $i$ with $1 \leq i \leq k$,consider the complete graph on $n_i$ vertices. How many edges does this graph have?  I thought of making graphs and figuring out a relation but still wasnt able to.
57506
I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently.  I checked for proofs here   I couldn't have figured out the combinatorial proof by myself, and the inductive proof assumes you already know the answer...  So my question is : do you know how to prove directly through computation that $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ ?
66723
The question: Let $f_n$ be fibonacci numbers. Prove: $\sum_{k=0}^{n-1} \binom{n+k}{2k+1} = f_{2n-1}$ and $\sum_{k=0}^n \binom{n+k}{2k} = f_{2n}$  For every $n\in N$.  $f_0=f_1=1$, $f_n=f_{n-1}+f_{n-2}$ for $n\ge 2$  I'm supposed to do this through induction.  What I did, first, is that I've seen that for $1$ both statements are true, then assumed for $n$.  For $n+1$ I got that the first sum is equal to the first sum for $n$ and the second sum for $n$, which under the definition of fibonacci numbers, makes the assumption true.  Similarly I did the process for the second sum.  Is this all that I had to do to solve this problem? What's bugging me is that I need to use both of the sums for a certain $n$ in proving that either one of those sums is valid for $n+1$, which I haven't encountered yet in exercises containing induction.
109886
I have to give a combinatorial proof of  $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$  I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have algorithms to solve most problems. Usually I won't just "see" solutions unless I have a thorough enough understanding of a theory. This is also the case here. I know what the symbols mean, but I don't see what I should count and how to obtain the identity.  I think the right-hand side counts $n$-element subsets of a $(2n-1)$-element set with one element chosen to be "special". I think I should find a partition of the set of such subsets into $n$ parts so that the left-hand side is the sum of the cardinalities of the parts. Is there $n$ of anything on the right-hand side? Well, there are $n$ choices for the "special" elements, but only after I've chosen the $n$-element subset. Otherwise I can choose the "special element" in $2n-1$ ways.  This is a homework problem so I probably shouldn't ask for a full solution. But I would like to have some guidelines for approaching such problems, perhaps based on this example.
80878
I need a hand in showing that $$ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$$   Thanks in advance for any help.
64537
Prove that for every positive integer $n \ge 2$ $$\sum^n_{k=1}k \sqrt{\binom nk}\leq\sqrt{2^{n-1}n^3}$$ I tried it by induction but I didn't know how to end it.
100655
I am to find a combinatorial argument for the following identity:  $$\sum_k \binom {2r} {2k-1}\binom{k-1}{s-1} = 2^{2r-2s+1}\binom{2r-s}{s-1}$$  For the right hand side, I was think that would just be number of ways to choose at least $s-1$ elements out of a $[2r-s]$ set. However, for the left hand side, I don't really know what it is representing.   Any help would be greatly appreciated!
96204
I'm looking for some guidance in solving this. I have read through my text multiple times trying to find something similar to this and I'm coming up with nothing. I'm not really sure where to start on solving this problem.  The question simply states     Prove that ${{n}\choose{k}} = {{n - 2}\choose{k}} + 2{{n - 2}\choose{k - 1}} + {{n - 2}\choose{k - 2}}$.   I'm very new to binomial coefficients, and extremely lost.
113476
I got stuck at the computation of the sum  $$ \sum\limits_{k=0}^n (-1)^k{2n-k\choose k}. $$ I think there is no purely combinatorial proof here since the sum can achieve negative values. Could you give me solution, it seems to involve generating functions.
15045
I want to prove this equation, $$ \binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a} $$ I thought of proving this equation by prove that you are using different ways to count the same set of balls and get the same result. But I'm stuck. Help me please.   (Presumptive) Source: Theoretical Exercise 1.14(a), P19, A First Course in Pr, 8th Ed, by S Ross.
17936
Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$.  Writing out several terms, I think the answer is $1/(n+1)$, but I'm struggling to prove this. I would greatly appreciate it if someone could show how to prove this.
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!