I am trying to evaluate a sum involving binomial coefficients, and by some manipulations, I have reduced it to $$\sum_{i=0}^{n} \binom{n+i}{i} 2^{n-i}$$ where $n$ is a constant ($n=1009$ in my particular case). (This looks like the LHS of the Hockey Stick Identity, except for the presence of the $2^{n-i}$ term. I would also be interested in further generalisation, replacing the $2$ by an arbitrary constant).  To evaluate this, I attempted writing $$2^{n-i} = \sum_{k=0}^{n-i} \binom{n-i}{k}$$ which gave a more symmetric expression, but otherwise didn't seem to help much.  So, given that the answer (according to Mathematica) is $4^n$, how can this be proved?
19041
I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$  I know that $$2^n = \sum\limits_{k=0}^n \binom{n}{k}$$ but that didn't help me
122267
I still haven't quite realized how to solve binomial coefficient problems like this, can someone show me an elaborated way of solving this?  I need to write this expression in a more simplified way: $\sum_{k=0}^{10} k \pmatrix{10 \\ k}\pmatrix{20 \\ 10-k}$  I'm aware of the binomial identity $\sum_{k=i}^{n-j}\binom{k}{i}\binom{n-k}{j}=\binom{n+1}{j+1}$  Just can't seem to see how to use it.  Many thanks.
75307
How can I show that  $$ \sum_{i=1}^{n-1}i=\binom{n}{2}? $$  This is what I have tried, but I do not know if it is correct:  Proof.  Let $n=2$. Then,  $$ \begin{align} \sum_{i=1}^{1}i&amp;=1\text{, and}\\ \binom{2}{2}&amp;=1. \end{align} $$  Hence, it holds. Assume that this is true for $k$. Then, we show that it is also true for $k+1$:  $$ \begin{align} \sum_{i=1}^{k}i=k+\sum_{i=1}^{k-1}i&amp;=k+\binom{k}{2}\\ &amp;=k+\frac{k!}{2(k-2)!}\\ &amp;=k+\frac{k(k-1)}{2}\\ &amp;=\frac{k(k+1)}{2}\\ &amp;=\frac{(k+1)!}{2!(k-1)!}=\binom{k+1}{2}.\square \end{align} $$  Also, proofs by induction are confusing to write. Is there a standard "skeleton" for them I can use?
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  .
29977
A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.
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?
23936
How do I evaluate $\sum_{k=0}^{n} {n \choose k}{m \choose k}$ for a given $n$ and $m$.  I have tried to use binomial expansion and combine factorials, but I have gotten nowhere. I don't really know how to start this problem.  The answer is ${n+m \choose n}$. Any help is greatly appreciated.  EDIT: I'm looking for  a proof of this identity.
43096
Find a closed form expression for $$\sum_{r=0}^n \dfrac{(-1)^r}{\dbinom{n}{r}}$$ where $n$ is an even positive integer.  I tried using binomial identities, but since the binomial coefficient is in the denominator, I can't do much. Also, I'm seeking a non-calculus, elementary solution, if possible. Thanks.
45758
I'm studying for a midterm and need some help with proving summation     $$\sum\limits_{k=0}^n\binom{n}{k}2^k = 3^n$$   using the binomial theorem.  This is what I've been thinking so far:   In the binomial theorem, we set $x = 0$ and $y = 2$, so:  $3^n = (x+y)^n = \sum\limits_{k=0}^n\binom{n}{k}y^k$  $ = \sum\limits_{k=0}^n\binom{n}{k}2^k$  Am I getting this correct so far or completely wrong? Any help would be appreciated. Thanks.
60398
I'm wondering if there is a formula for the value of $(1+i)^n+(1-i)^n$?  I calculated the first terms starting with $n=1$ to be, in order, $2$, $0$, $-4$, $-8$, $-8$, $0$, $16$, $\dots$  So it seems to be some sequence of positive and negative powers of $2$ with $0$s thrown in. Is there a more explicit formulation of what $(1+i)^n+(1-i)^n$ is, based on $n$?   With the binomial theorem, I get it equal to $$ \sum_{k=0}^n\binom{n}{k}i^{n-k}(1+(-1)^{n-k}). $$ Can this be made nicer? Thanks.
7156
Prove that   $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$   I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement then $|S| + |S^\prime| = n$" was also given, but I still don't know how to begin.
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.
68476
Here's how it is.  So I was studying some notes on Discrete Structures then I discovered this. Prove that $2^N = \binom{N}{0} + \binom{N}{1} + \binom{N}{2} + \dots + \binom{N}{N}$ Since I was new to this, I didn't quite understand it.  I tried using the binomial expansion but it confused me a little.  Can someone please help me solve this.  That would be great.
89273
$$\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+...+\binom{n}{n-1}\binom{n}{n}$$   All I could think of so far is to turn this expression into a sum. But that does not necessarily simplify the expression. Please, I need your help.
57034
Determine the value of $\displaystyle \sum_{k=n}^{2n} \binom{k} {n} 2^{-k}$ for $n \geq 1$  My attempt: I have asked this question before in another math forum but it leads no solution. My friend suggested me to search for something like series-k. I also looked at my textbook in combinatoric section (which apparently leads to Binomial Theorem), but really I don't have any idea for this one.  Could you help me?
96036
Evaluate: $$ \sum _ {k=1}^{n}{\frac{k}{n}\dbinom{n}{k}t^k(1-t)^{n-k}} $$  $\dbinom{n}{k}$stands for the usual binomial coefficient giving the number of ways of choosing $k$ objects from n objects.    Totally stuck.How can I able to solve this?
23708
Find the value of $\sum_{k=1}^{n}k\binom{n}{k}$ ?    I know that $\sum_{k=0}^{n}\binom{n}{k}= 2^{n}$ and so, $\sum_{k=1}^{n}\binom{n}{k}= 2^{n}-1$ but how to deal with $k$ ?