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)

8
votes
2answers
598 views

Is there a combinatorial way to see the link between the beta and gamma functions?

The Wikipedia page on the beta function gives a simple formula for it in terms of the gamma function. Using that and the fact that $\Gamma(n+1)=n!$, I can prove the following formula: $$ ...
8
votes
3answers
290 views

When are products of binomial coefficients equal?

It's known that $\binom{n}{r} = \binom{n}{s}$ if and only if $r = s$ or $r = n - s$. If $n \neq m$, is it true that $\binom{n}{s} \binom{m}{r} = \binom{n}{k} \binom{m}{\ell}$ if and only if ($s = k$ ...
8
votes
2answers
104 views

Rough bound for sum $\binom{3n}{0}+\binom{3n}{1}+\cdots+\binom{3n}{n-1}$

Is it true that $$\frac{\dbinom{3n}{0}+\dbinom{3n}{1}+\cdots+\dbinom{3n}{n-1}}{2^{3n}}<\frac13$$ for all positive integers $n$? I've plotted the first few values of $n$ and noticed that the ...
8
votes
2answers
231 views

Find the sum of this series :$ \frac{1}{{1!2009!}} + \frac{1}{{3!2007!}} + \cdots + \frac{1}{{1!2009!}}$

Find the sum of this series : $$\sum\limits_{\scriptstyle 1 \leqslant x \leqslant 2009 \atop {\scriptstyle x+y=2010 \atop \scriptstyle {\text{ }}x,y{\text{ odd}} }} {\frac{1}{{x!y!}}} = ...
8
votes
5answers
10k views

Proving $ { 2n \choose n } = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!} $

How to prove this binomial identity : $$ { 2n \choose n } = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!} $$ The left hand side arises while solving a standard binomial problem the right hand ...
8
votes
3answers
252 views

A peculiar binomial coefficient identity

While inventing exercises for a discrete math text I'm writing I came up with this $$ \binom{\binom{n}{2}}{2}=3\binom{n+1}{4} $$ It's an easy result to prove, but it got me wondering Is this pure ...
8
votes
2answers
2k views

prime numbers in Pascal's triangle

Just wondering about this: Is it true that there are no prime numbers in Pascal's triangle, with the exception of $\binom{n}{1}$ and $\binom{n}{n-1}$? From the first 18 lines it appears that this is ...
8
votes
3answers
246 views

Putting ${n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ in a closed form

As the title says, I'm trying to transform $\displaystyle{n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ into a closed form. My work: $\displaystyle\left(1 + ...
8
votes
3answers
422 views

Polynomial in $\mathbb{Q}[x]$ sending integers to integers?

We can view the binomial coefficient $\binom{x}{k}$ has a polynomial in $x$ with degree $k$. So taking some $f\in\mathbb{Q}[x]$, why is $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$, precisely when the ...
8
votes
4answers
563 views

Inequality with central binomial coefficients

For every even positive number $N$ we have: $$ {2N \choose N } < 2^N {N \choose N/2 } < 2 {2N \choose N } $$ (Furthermore, $\frac{2^N {N \choose N/2 }}{{2N \choose N }} \to \sqrt{2} $ for ...
8
votes
4answers
167 views

Prove: ${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-…(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}$

Prove: $${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-...(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}$$ $(2n+1)!!$ is a factorial of odd integers, ...
8
votes
4answers
325 views

Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

How can I calculate the following sum involving binomial terms: $$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$ Where the value of n can get very big (thus calculating the binomial ...
8
votes
3answers
163 views

Prove that $\sum\limits_{k}\sum\limits_{i\le k}\binom{n}{i}\cdot\sum\limits_{j>k}\binom{n}{j}=\frac{n}{2}\binom{2n}{n}$

Question: show that $$\sum_{k=0}^{n-1}\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\right)\left(\binom{n}{k+1}+\cdots+\binom{n}{n}\right)=\dfrac{n}{2}\binom{2n}{n}$$ My idea: let ...
8
votes
4answers
813 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: ...
8
votes
3answers
412 views

Non-probabilistic proofs of a binomial coefficient identity from a probability question

Combining the answers given by me and Ralth to the probability question at Probability Question, we get the following identity: $$ \sum\limits_{k = m}^n {{n \choose k}p^k (1 - p)^{n - k} {k \choose ...
8
votes
5answers
572 views

Choice Problem: choose 5 days in a month, consecutive days are forbidden [duplicate]

I'm "walking" through the book "A walk through combinatorics" and stumbled on an example I don't understand. Example 3.19. A medical student has to work in a hospital for five days in January. ...
8
votes
3answers
113 views

Show that ${-n \choose i} = (-1)^i{n+i-1 \choose i} $

Show that ${-n \choose i} = (-1)^i{n+i-1 \choose i} $. This is a homework exercise I have to make and I just cant get started on it. The problem lies with the $-n$. Using the definition I get: $${-n ...
8
votes
2answers
805 views

Binomial coefficients: how to prove an inequality on the $p$-adic valuation?

In section 4 of the article by Afred van der Poorten's A Proof That Euler Missed ... the following inequality is used: $$\nu_{p}\displaystyle\binom{n}{m}\leq\left\lfloor\dfrac{\ln n}{\ln ...
8
votes
3answers
415 views

A Curious Binomial Sum Identity without Calculus of Finite Differences

Let $f$ be a polynomial of degree $m$ in $t$. The following curious identity holds for $n \geq m$, \begin{align} \binom{t}{n+1} \sum_{j = 0}^{n} (-1)^{j} \binom{n}{j} \frac{f(j)}{t - j} = (-1)^{n} ...
8
votes
2answers
239 views

Ordinary generating function for $\binom{3n}{n}$

The ordinary generating function for the central binomial coefficients, that is, $$\displaystyle \sum_{n=0}^{\infty} \binom{2n}{n} x^{n} = \frac{1}{\sqrt{1-4x}}$$ follows from the generalized ...
8
votes
2answers
273 views

Combinatorial proof: $p^{r-n}$ divides $\binom{p^{r-2}}{n}$

Let $p$ be an odd prime. Then if $1<n<r$, $$p^{r-n}\,\left|\,\binom{p^{r-2}}{n}\right.$$ Does anyone have a clever combinatorial proof of this fact? There's an easy argument just by counting ...
8
votes
3answers
109 views

How to prove that $\frac1{n\cdot 2^n}\sum\limits_{k=0}^{n}k^m\binom{n}{k}\to\frac{1}{2^m}$ when $n\to\infty$

I have solve following sum $$\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}\Longrightarrow \dfrac{\displaystyle\sum_{k=0}^{n}k\binom{n}{k}}{n\cdot 2^n}\to\dfrac{1}{2},n\to\infty$$ ...
8
votes
5answers
205 views

Proving a binomial sum with simple result

In deriving a formula I've come up with an expression that I need to prove, specifically: $$(-1)^n = \sum_{j=1}^n (-1)^j \binom{n+1}{j+1} j^n$$ where $n$ is a positive integer. This seems ...
8
votes
2answers
890 views

Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

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 ...
8
votes
1answer
286 views

Smallest constant in exponent so that limit of sum is $0$

I am trying to work out the smallest constant $c>0$ so that $$\lim_{n \to \infty} \sum_{a=1}^n \sum_{b=0}^n {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}} =0 .$$ ...
8
votes
3answers
349 views

How prove this $\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $

I think the following equality is true ($p\in \mathbb{N},p\ge 2$): $$\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $$ when $p=2$, then ...
8
votes
3answers
197 views

How can we find the gcd for elements (binomial coefficient)?

$\gcd\left(\binom{2n}1,\binom{2n}3,\binom{2n}5,\ldots,\binom{2n}{2n-1}\right)$ i want to know what is specialty of such a series.I am not able to generalize the problem solution.Is there any rule for ...
8
votes
1answer
3k views

Intuition behind negative combinations

Take $\binom{n}{r}$. It denotes how in how many different ways you can choose $r$ elements from a set of $k$ elements. For case $\binom{4}{3}$ which evaluates to $\frac{4!}{3!(4-3)!}=4$, it perfectly ...
8
votes
2answers
303 views

Binomial identity

I'd like to get a hint to prove the following identity: $$\tag{1}\sum_{\nu}(-1)^{\nu}\displaystyle \binom{a}{\nu}\binom{n-\nu}{r}=\binom{n-a}{n-r} .$$ The original statement reads "By specialization ...
8
votes
1answer
396 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
8
votes
4answers
188 views

A binomial identity from Mathematical Reflections

Here is the problem: Let $m,n$ be positive integers with $n>m$. Prove that $\displaystyle\sum_{k=0}^{\lfloor\frac{n+m}2\rfloor} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$ This ...
8
votes
1answer
455 views

Evaluate $\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$

Evaluate $$\lim_{n \to \infty} \sum_{j=0}^{n}{{j+n-1} \choose j}\frac{1}{2^{j+n}}$$ I don't understand where to start. Please help.
8
votes
1answer
260 views

Combinatorial proof that $\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}$

This recent question contains two proofs that $$\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}.$$ One, by Antonio Vargas, uses a double integral. The other, by me, uses the ...
8
votes
1answer
195 views

Product of binomial coefficient as a basis

I am stuck with the following problem. Every polynomial of degree $d$ can be expressed as $$ p(x) = p_d \binom{x}{d}+ p_{d-1}\binom{x}{d-1} + \cdots + p_0 \binom{x}{0} $$ What is the ...
8
votes
2answers
216 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
8
votes
2answers
313 views

Does this really converge to 1/e? (Massaging a sum)

Short version: can we prove that $$\sum_{k=0}^n (-1)^k \binom{n}{k}^2 \frac{k!}{n^{2k}} \to \frac1e$$ as $n \to \infty$? Long version: First, consider $$a_n = \sum_{k=0}^n \frac{(-1)^k}{k!}$$ It is ...
8
votes
1answer
402 views

Vandermonde identity in a ring

Let $R$ be a commutative $\mathbb{Q}$-algebra. For $r \in R$ and $n \in \mathbb{N}$ we can define the binomial coefficient $\binom{r}{n}$ as usual by $\binom{r}{0}=1$ and ...
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 ...
8
votes
1answer
498 views

Combinatorial Interpretation of Fractional Binomial Coefficients

My question is a bit imprecise - but I hope you like it. I even strongly think it has a proper answer. The binomial coefficient $\binom{\frac{1}{2}}{n}$ is strongly related to Catalan numbers - the ...
8
votes
1answer
383 views

Derivation of bound on expression involving binomial coefficient from Erdős and Rényi 1959

I'm in the process of working through Erdős and Rényi's 1959 article "On Random Graphs I". In the proof of the first Lemma, equation 14 gives a bound on an expression involving several binomial ...
8
votes
1answer
438 views

$\binom{n}{k} : \binom{n}{k+1} : \binom{n}{k+2} = a : b : c$

It is a rather surprising fact (to me, at least) that $\displaystyle \binom{14}{4} = 1001$; $\displaystyle \binom{14}{5} = 2002$; $\displaystyle \binom{14}{6} = 3003$. Actually, this is the only ...
7
votes
6answers
599 views

Closed-form expression for $\sum_{k=0}^n\binom{n}kk^p$ for integers $n,\,p$

Is there a closed-form expression for the sum $\sum_{k=0}^n\binom{n}kk^p$ given positive integers $n,\,p$? Earlier I thought of this series but failed to figure out a closed-form expression in $n,\,p$ ...
7
votes
2answers
755 views

Finding $\lim\limits_{n \to \infty} \sum\limits_{k=0}^n { n \choose k}^{-1}$

We know that $$ 2^n= (1+1)^n = \sum_{k=0}^n {n \choose k}$$ I was asked to solve this limit, $$\lim_{n \to \infty} \ \sum_{k=0}^n {n \choose k}^{-1}=? \quad \text{for} \ n \geq 1$$
7
votes
4answers
6k views

Derivation of binomial coefficient in binomial theorem.

How was the binomial coefficient of the binomial theorem derived? $$\frac{n!}{k!(n-k)!}$$
7
votes
5answers
278 views

Is this combinatorial identity a special case of Saalschutz's theroem?

When I solved a question, the following combinatorial identity was used $$ \sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}. $$ But to prove this identity is ...
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? ...
7
votes
3answers
484 views

After 6n roll of dice, what is the probability each face was rolled exactly n times?

This is closely related to the question "If you toss an even number of coins, what is the probability of 50% head and 50% tail?", but for dice with 6 possible results instead of coins (with 2 possible ...
7
votes
3answers
527 views

Hard elementary combinatorics problem

How does one compute (without brute force) the smallest integer $n$ such that $\binom{2n}{1}(-3)^0 + \binom{2n}{3}(-3)^1 + \binom{2n}{5}(-3)^2 + \cdots + \binom{2n}{2n-1}(-3)^{(n-1)} = 0$?
7
votes
4answers
449 views

Showing that $\lceil (\sqrt{3} + 1)^{2n} \rceil$ is divisible by $2^{n+1}$.

I have a question which has fluxommed me and my pals for the past few days. Any help or solution is welcome Show using Binomial theorem that the integer just after $(3^{1/2} + 1)^{2n}$ is divisble ...
7
votes
3answers
842 views

Summation Identity: $\sum_{i=1}^ni^3 = \left( \frac{n(n+1)}{2} \right)^2$

I have to prove: $$\sum\limits_{i = 1}^n i^3 = \Bigg( \frac{n(n+1)}{2}\Bigg)^2$$ Using the following: $$n^3 = 6 {n \choose 3} + 6 {n \choose 2} + n \quad \forall n \in \mathbb{N}$$ My work is that ...