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)

12
votes
1answer
483 views

New Year Combinatorics 2015

In the spirit of the festive period and in appreciation of the encouraging response to my X'mas Combinatorics problem posted recently, here's one for the New Year! Express the following as a ...
12
votes
5answers
265 views

Sum $\displaystyle \sum_{n=i}^{\infty} {2n \choose n-i}^{-1}$

$\displaystyle \sum_{n=i}^{\infty} {2n \choose n-i}^{-1}=\sum_{n=i}^{\infty} \frac {1}{{2n \choose n-i}}$ is a very interesting one. Here is what I have from WolframAlpha. $\displaystyle \sum_{n=0}^{\...
12
votes
2answers
216 views

An interesting property of binomial coefficients that I couldn't prove

So when I was trying to prove the argument in this link I've come up with something. When you extract the left term from the right term, you get the term under them. What is interesting is that as ...
12
votes
2answers
334 views

A conjecture including binomial coefficients

Question: $$\sum_{k=1}^{n}k\binom{2n}{n+k}=\frac n2\binom{2n}{n}$$ is true for every $n\in \mathbb N$? If this is true, then how can we prove this? When I was playing with numbers, I conjectured ...
12
votes
2answers
662 views

Show $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ by block-walking interpretation of Pascal's triangle

A combinatorial proof for the identity $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$ is the following "committee" argument, which seems the most common. There are $\binom{n}{k}$ ...
12
votes
1answer
160 views

Prove $\sum_{i=0}^n \binom{n}{i}^2x^{n-i} = 0$ has $n$ negative roots

Let's $n \in \mathbb{Z^+}$, how to $\text{prove}|\text{disprove}$ that: the equation $\boxed{\sum_{i=0}^n \binom{n}{i}^2x^{n-i} = 0}$ has exactly $n$ distinct negative roots. My friend get ...
12
votes
2answers
299 views

The Fermat prime 257 and binomial sum $\sum_{n=0}^\infty \frac{(-1)^n}{\binom {8n}{4n}}$?

We have, $\begin{aligned} \sum_{n=0}^\infty \frac{(-1)^n}{\binom n{n/2}} &= \frac{4}{27}(9-\pi\sqrt{3}\,)\\[2.5mm] \sum_{n=0}^\infty \frac{(-1)^n}{\binom {2n}n} &= \frac{4}{5} - \frac{4\sqrt{...
12
votes
3answers
142 views

Prove $\sum_{q=\alpha}^p \binom{q}{\alpha} \binom{p}{q}\frac{(-1)^q(-q)^p}{q^\alpha}=\frac{p!}{\alpha!}.$

How to prove $\displaystyle \sum_{q=\alpha}^p \binom{q}{\alpha} \binom{p}{q}\frac{(-1)^q(-q)^p}{q^\alpha}=\frac{p!}{\alpha!}$ for $1 \leq \alpha \leq p$? EDIT: This is a result that I derived ...
12
votes
4answers
507 views

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity i.e....
12
votes
1answer
771 views

Counting subsets with r mod 5 elements

Some time ago Qiaochu Yuan asked about counting subsets of a set whose number of elements is divisible by 3 (or 4). The story becomes even more interesting if one asks about number of subsets of n-...
12
votes
1answer
189 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
12
votes
1answer
179 views

Is the given binomial sum almost everywhere negative as $K\to\infty$?

The binomial sum is as follows: $$\mathcal {L}^K(\theta)= \sum_{i=\lceil{K/2}\rceil}^K \binom{K}{i}\theta^i\left((1-\theta)^{K-i}-\frac{1}{2}(1-\theta)^{-K}(1-2\theta)^{K-i}\right)$$ which can also ...
11
votes
6answers
661 views

Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$ [duplicate]

I need to evaluate, for a certain worded question: If n is even $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n}$$ If n is odd $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots\binom{n}{n-...
11
votes
6answers
320 views

Why, conceptually, is it that $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$? [duplicate]

Why, conceptually, is it that $$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}?$$ I know how to prove that this is true, but I don't understand conceptually why it makes sense.
11
votes
5answers
710 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 ...
11
votes
7answers
1k views

Proof of the Hockey-Stick Identity: $\sum_{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}.$$ What's the name of this identity? Is it the identity of the Pascal's triangle ...
11
votes
5answers
453 views

How to prove that $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ is $0$ for $j < p$ and $p!$ for $j = p$

Let $p \in \mathbf{N}$. I don't know how to prove that $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$$ and $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$$ (...
11
votes
3answers
789 views

Binomial Identity $\sum\binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$

I'm looking for a reference with the proof of the following binomial identity: $$\sum_{k=0}^n \binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$$ I've looked in a number of textbooks that have a ...
11
votes
3answers
858 views

How to get ${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$

I found this in my test book, any hints? Given $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$$ Then find the value of x and y in n. According to the answer ...
11
votes
7answers
553 views

Summation simplification $\sum_{k=0}^{n} \binom{2n}{k}^2$

$\sum_{k=0}^{n} \binom{2n}{k}^2$ So i'm trying to simplify this one and I'm stuck in nowhere. Some kind of tip would be appreciated. Thanks! :)
11
votes
3answers
220 views

Calculating $\sum_{0\le k\le n/2} \binom{n-k}{k}$

I would like to evaluate: $$\sum_{0\le k\le n/2}\binom{n-k}{k}$$ Any idea?
11
votes
4answers
470 views

Show that if $\prod\limits_{k=1}^{n}(x+a_k)=\sum\limits_{k=0}^{n} {n\choose k}a^k_kx^{n-k}$ then $a_1=a_2=a_3=…=a_{n-1}=a_n$

Let $a_0=1$. Prove that, if $$\prod_{k=1}^{n}(x+a_k)=\sum_{k=0}^{n} {n\choose k}a^k_kx^{n-k}=x^n+{n\choose 1}a_1x^{n-1}+{n\choose 2}a^2_2x^{n-2}+....+a^n_n,$$ then $a_1=a_2=a_3=....=a_{n-1}=a_n$. ...
11
votes
2answers
223 views

Complicated sum with binomial coefficients

I know how to prove, that $\frac{1}{2^{n}}\cdot\sum\limits_{k=0}^nC_n^k \cdot \sqrt{1+2^{2n}v^{2k}(1-v)^{2(n-k)}}$ tends to 2 if n tends to infinity for $v\in (0,\, 1),\ v\neq 1/2$. This can be proved ...
11
votes
4answers
306 views

Determine $\displaystyle \lim_{n \to \infty}{{n} \choose {\frac{n}{2}}}\frac{1}{2^n}$, where each $n$ is even

For each positive even integer $n$, set $$P_n = \displaystyle {{n} \choose {\frac{n}{2}}}\frac{1}{2^n}.$$ Show that $\displaystyle \lim_{n \to \infty} P_n$ exists and determine its value. Here's ...
11
votes
3answers
207 views

Prove the identity $ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$

$$ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$$ Class themes are: Generating functions and formal power series.
11
votes
1answer
976 views

Sum of product of binomial coefficient

Is the following true? $$\sum_{x_1+x_2+...+x_n=n}\ \ \, \prod_{i=1}^{n}{k_i\choose x_i}={\sum_{i=1}^{n}k_i \choose n} .$$ I tried to use the multinomial theorem, but it doesn't seem applicable.
11
votes
3answers
385 views

Proof of the identity $\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}$

Prove the identity: $$\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}.$$
11
votes
1answer
316 views

Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$

For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$. LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset. RHS: We are ...
11
votes
3answers
307 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\;\sum_{j=0}^{2l-n}\binom{l}{j}$$ Ideally it should be possible to evaluate it exactly using some ...
11
votes
2answers
581 views

Closed form for a sum involving binomial coefficients

Let $n,k$ be positive integers. Is there a closed form of the sum $$\sum_{s=0}^{k} \binom{n}{s} \binom{s}{k-s}\text{?}$$ By that I mean a representation which is free of sums and hypergeometric ...
11
votes
2answers
142 views

What are the “numerator” and “denominator” of binomial coefficients called?

Do the numbers $n$ and $k$ in the binomial coefficient $\binom nk$ have a name? For the fraction $\frac nk$ we would use numerator and denominator. But I have not seen some terminology for binomial ...
11
votes
1answer
199 views

Interpretation of a combinatorial identity

I am trying to find an combinatorial interpretation for the following combinatorial identity involving iterated binomial coefficients, which appeared in the November 1980 edition of The American Math ...
11
votes
3answers
647 views

Prove the lecturer is a liar…

I was given this puzzle: At the end of the seminar, the lecturer waited outside to greet the attendees. The first three seen leaving were all women. The lecturer noted " assuming the attendees are ...
11
votes
1answer
178 views

Curious combinatorial summation

Let $\gamma$ denote a grid walk from the upper left corner $(1,k)$ to the lower right corner $(\ell,1)$ of the $k\times\ell$ rectangle $\{1,..,k\}\times\{1,..,\ell\}$. There are $\binom{k+\ell-2}{k-1}...
11
votes
3answers
320 views

Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$

Is it possible to write this in closed form: $$\sum_{k=0}^{n} k\binom{n}{k}\log\left(\vphantom{\Huge A}\binom{n}{k}\right)$$ Can you get something like $$n2^{n-1}\log(2^{n-1})$$
11
votes
2answers
587 views

Techniques for summing ratio of binomial coefficients

There are several identities that involve the sum of the product of binomial coefficients. However what I am searching for is an identity that involves the ratio of binomial coefficients. Specifically,...
11
votes
1answer
787 views

Factorial canceling on expansion of binomial coefficients on Concrete Mathematics

On Concrete Mathematics section 5.5, which is teaching the hypergeometric functions, generalized factorials is defined as: \[ \frac 1 {z!} = \lim_{n \to \infty} \binom{n+z}{n}n^{-z} \] where \[ \...
11
votes
0answers
181 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
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 ...
10
votes
4answers
234 views

Inequality $\binom{2n}{n}\leq 4^n$

I would like to prove the following inequality, for $n=0,1,2,...$, $$ \binom{2n}{n}\leq 4^n.$$ I already proved it by induction, and I'm looking for another proof.
10
votes
2answers
316 views

Proving that $\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b$

Prove that for all positive integers $b$ that $$\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b.$$ My idea is induction, but I cannot figure stuff out on the inductive step.
10
votes
2answers
1k views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
10
votes
2answers
357 views

The integral $\int_0^1 \frac{(x+1)^n-1}{x} dx$

I know that the integral $\int_0^1 \frac{(x+1)^n-1}{x} dx,$ for $n \in \mathbb{Z}^+$, can be evaluated by expanding the numerator with the binomial theorem and integrating term by term. You get the ...
10
votes
3answers
190 views

Is there a closed form or approximation to $\sum_{i=0}^n\binom{\binom{n}{i}}{i}$

I tried to calculate the sum $$ \sum_{i=0}^n\binom{\binom{n}{i}}{i} $$ but it seems that all my known methods are poor for this. Not to mention the intimate recursion, that is $$ \sum_{i=0}^n\binom{\...
10
votes
6answers
216 views

A limit on binomial coefficients

Let $$x_n=\frac{1}{n^2}\sum_{k=0}^n \ln\left(n\atop k\right).$$ Find the limit of $x_n$. What I can do is just use Stolz formula. But I could not proceed.
10
votes
3answers
576 views

proof that $1 = \sum\limits_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$

I'm looking for a proof of this identity: $$ 1 = \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k} $$ I'll take anything, but a combinatorial proof would be nice - all of the terms in the sum ...
10
votes
2answers
147 views

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $\sum_{k=1}^n\frac{a_k-b_k}k$

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $$\sum_{k=1}^n\frac{a_k-b_k}k$$ By computing some partial sums, the answers are 0. It seems an inductive argument is possible.
10
votes
3answers
247 views

A sum with binomial coefficients

Show that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^{n+2}=\frac{2^{n}n(n+2)!}{6}.$$
10
votes
2answers
101 views

When is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $n,m,j$?

As stated in the title: when is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $m,j,n$? I was thinking about this problem a couple of days ago because in all my years of ...
10
votes
3answers
447 views

Problem of limit with binomial coefficients

I thought that the following would made a nice exercise, but I am not sure how to evaluate its difficulty since I often miss elementary solutions. How about you try answering it? It would be great to ...