All Questions
Tagged with binomial-coefficients combinatorics
740
questions
77
votes
20
answers
24k
views
Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
After reading this question, the most popular answer use the identity
$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1},$$
or, what is equivalent,
$$\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}.$$
What's ...
- 1,620
91
votes
9
answers
106k
views
Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$
I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$.
I already know the logical Proof:
$${n \choose k}^2 = {...
- 911
99
votes
4
answers
13k
views
Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$
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 ...
- 1,520
34
votes
12
answers
39k
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= ${{n}...
user6639
10
votes
7
answers
24k
views
How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?
How can we prove that
$$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$
(Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
- 3,909
15
votes
4
answers
6k
views
Prove $\sum\limits_{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?
- 1,919
13
votes
7
answers
10k
views
Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$ [duplicate]
Let $n$ be a positive integer. Prove that
\begin{align}
\sum_{k=0}^n \left(-1\right)^k \binom{n}{k} = 0 .
\end{align}
I tried to solve it using induction, but that got me nowhere. I think the ...
- 1,324
21
votes
6
answers
19k
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.
$$
\mbox{I failed to prove that}\quad
\binom{n-k+1}{k}=...
- 966
24
votes
5
answers
10k
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 ...
- 15.5k
7
votes
1
answer
455
views
Why is flipping a head then a tail a different outcome than flipping a tail then a head?
In either case, one coin flip resulted in a head and the other resulted in a tail. Why is {H,T} a different outcome than {T,H}? Is this simply how we've defined an "outcome" in probability?
My main ...
- 2,331
13
votes
2
answers
14k
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 ...
- 6,315
33
votes
6
answers
19k
views
How do you prove ${n \choose k}$ is maximum when $k$ is $ \lceil \tfrac n2 \rceil$ or $ \lfloor \tfrac n2\rfloor $?
How do you prove $n \choose k$ is maximum when $k$ is $\lceil n/2 \rceil$ or $\lfloor n/2 \rfloor$?
This link provides a proof of sorts but it is not satisfying. From what I understand, it focuses on ...
- 1,183
22
votes
10
answers
5k
views
Truncated alternating binomial sum
It is easily checked that
$\displaystyle\sum_{i\ =\ 0}^{n}\left(\, -1\,\right)^{i} \binom{n}{i} = 0$, for example by appealing to the binomial theorem.
I'm trying to figure out what happens with the ...
- 693
12
votes
3
answers
5k
views
Proof of a combinatorial identity: $\sum\limits_{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? Although a ...
- 307
5
votes
2
answers
2k
views
Combinatorial interpretation for Vandermonde's 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.
- 51