Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

6
votes
4answers
667 views

Prove $\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) [duplicate]

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?
26
votes
4answers
19k views

Combinatorial proof of summation of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Can you guys help me prove this? There is a way of proving this logically but I was hoping to find a more "mathematical" proof, if possible. $$\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n ...
47
votes
2answers
4k views

Identity for convolution of central binomial coefficients

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
16
votes
6answers
3k views

Elementary central binomial coefficient estimates

How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ? Does anyone know any better elementary estimates?
14
votes
9answers
8k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

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= ...
10
votes
10answers
3k views

How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?

I am trying to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$ but am not able to think something except induction,which is of-course not necessary (I think) here, so I am ...
27
votes
6answers
11k views

Proof that a Combination is an integer

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 ...
12
votes
4answers
2k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
5
votes
3answers
321 views

Evaluating Combination Sum $\sum{n+k\choose 2k} 2^{n-k}$

Evaluate $$\sum_{k=0}^n{n+k\choose 2k} 2^{n-k}$$ So im not really sure how to begin with this. I would imagine we start with dividing out $2^{n}$, but not really sure much past that
6
votes
5answers
2k views

Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
7
votes
3answers
2k views

Proof of a combinatorial identity: $\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? ...
3
votes
4answers
3k views

Vandermonde's Identity : Summations with binomial coefficients

(Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross. Can someone help me solve this equation? How to prove that ...
10
votes
5answers
638 views

factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

The successive difference of powers of integers leads to factorial of that power. I think this is the formula $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$ But I found no proof on internet. Please ...
28
votes
1answer
3k views

How to reverse the $n$ choose $k$ formula?

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 ...
16
votes
8answers
3k views

Proving $\sum\limits_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$

Show that $$\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$$ So for odd $n$ we have an even number of terms. So $\binom{n}{k} = \binom{n}{n-k}$ which have opposite signs. Thus the sum is $0$. For even $n$ ...
8
votes
2answers
5k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
5
votes
2answers
896 views

Number of monomials of certain degree

Wikipedia says that the number of different monomials of degree $M$ in $N$ variables is $$\frac{(M+N-1)!}{M!(N-1)!}\; .$$ Can anyone explain why this is true?
29
votes
2answers
5k views

How do I count the subsets of a set whose number of elements is divisible by 3? 4?

Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that $\displaystyle \sum_{k=0}^{n} {n ...
27
votes
7answers
2k views

Prove: $\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx$ for $0 \leq k \leq n$

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 ...
21
votes
6answers
9k views

prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer

Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared. My thought process: The numerator is the product of the first n even ...
4
votes
1answer
616 views

Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

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.
6
votes
5answers
4k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any ...
6
votes
2answers
2k views

Show $\sum\limits_{n=0}^{\infty}{2n \choose n}x^n=(1-4x)^{-1/2}$

How do you prove that $\sum\limits_{n=0}^{\infty}{2n \choose n}x^n=(1-4x)^{-1/2}$? I tried to identify the sum as a binomial series, but the $4$ and the $-1/2$ puzzle me. (This series arises in ...
5
votes
4answers
304 views

Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$ I ...
5
votes
2answers
283 views

Proving Binomial Idenity without calculus

How to establish the following identities without the help of calculus: For positive integer $n, $ $$\sum_{1\le r\le n}\frac{(-1)^{r-1}\binom nr}r=\sum_{1\le r\le n}\frac1r $$ and $$\sum_{0\le r\le ...
14
votes
3answers
2k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

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 ...
5
votes
3answers
788 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
2
votes
3answers
800 views

Counting subsets containing three consecutive elements (previously Summation over large values of nCr)

Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$. ...
8
votes
7answers
1k views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
19
votes
6answers
2k views

Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: ...
3
votes
2answers
3k views

Sum of square binomial coefficients [duplicate]

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 ...
17
votes
4answers
716 views

How to prove $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$?

Other than the general inductive method,how could we show that $$\sum_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$$ Apart from induction,I tried with Wolfram Alpha to check the validity,but ...
26
votes
3answers
2k views

Is there a direct proof of this lcm identity?

The identity $\displaystyle (n+1) \text{lcm} \left( {n \choose 0}, {n \choose 1}, ... {n \choose n} \right) = \text{lcm}(1, 2, ... n+1)$ is probably not well-known. The only way I know how to prove ...
14
votes
4answers
3k views

$C(n,p)$: even or odd?

Can we determine if a binomial coefficient $C(n,p)$ is even or odd, without calculating its value? ($p\lt n$, $p$ and $n$ are positive integers)
8
votes
4answers
801 views

Why does this expected value simplify as shown?

I was reading about the german tank problem and they say that in a sample of size $k$, from a population of integers from $1,\ldots,N$ the probability that the sample maximum equals $m$ is: ...
9
votes
6answers
990 views

Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?

How do I prove that $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$ I saw this in a book discussing generating functions.
4
votes
2answers
6k views

Number of even and odd subsets [duplicate]

Suppose we have the following two identities: $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ $\displaystyle \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$ The first says that the number of subsets ...
3
votes
5answers
410 views

Proving the total number of subsets of S is equal to $2^n$

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$. I realized that the total number of ...
4
votes
1answer
782 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...
4
votes
2answers
1k views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$ [duplicate]

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
5
votes
4answers
620 views

Proving a special case of the binomial theorem: $\sum^{k}_{m=0}\binom{k}{m} = 2^k$ [duplicate]

I want to know if I can get some help with this proof. I tried, but I just cannot seem to get $2^{k}$. It states that, For $k \in \mathbb{Z}_{\ge 0}$, $$\sum^{k}_{m=0}\binom{k}{m} = 2^k$$ Thank ...
2
votes
3answers
138 views

How to prove this statement: $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that Still a beginner here. Need to learn formatting. I am guessing by induction? Not sure what or how to go forward with this. Need help ...
1
vote
2answers
453 views

simple binomial theorem proof

I am trying to prove this binomial statement: For $a \in \mathbb{C}$ and $k \in \mathbb{N_0}$, $\sum_{j=0}^{k} {a+j \choose j} = {a+k+1 \choose k}.$ I am stuck where and how to start. My steps ...
29
votes
7answers
2k views

Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Let $m,n\ge 0$ be two integers. Prove that $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$ where $\delta_{mn}$ stands for the Kronecker's delta (defined by $\delta_{mn} = ...
17
votes
2answers
2k views

Combinatorial interpretation of Binomial Inversion

It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...
14
votes
6answers
937 views

How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?

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 ...
6
votes
1answer
2k views

Partial sum of rows of Pascal's triangle

I'm interested in finding $$\sum_{k=0}^m \binom{n}{k}, \quad m<n$$ which form rows of Pascal's triangle. Surely $\sum\limits_{k=0}^n \binom{k}{m}$ using addition formula, but the one above ...
5
votes
2answers
2k views

Why does the $n$-th power of a Jordan matrix involve the binomial coefficient?

I've searched a lot for a simple explanation of this. Given a Jordan block $J_k(\lambda)$, its $n$-th power is: $$ J_k(\lambda)^n = \begin{bmatrix} \lambda^n & \binom{n}{1}\lambda^{n-1} & ...
4
votes
2answers
12k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
3
votes
3answers
15k views

why is ${n+1\choose k} = {n\choose k} + {n\choose k-1}$? [duplicate]

Possible Duplicate: Proving ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$ can someone explain to me the proof of $${n+1\choose k} = {n\choose k} + ...