65 votes
Accepted

Reason for breakdown of a nice binomial identity

$\def\des{\operatorname{des}}$Let $\des(\pi)$ be the number of descents of the permutation $\pi$. Then for any permutation $\pi$ in $S_k$, we have \begin{equation*}\binom{xy+k-\des(\pi)-1}{k} =\sum_{\...
Ira Gessel's user avatar
  • 16.2k
50 votes
Accepted

New binomial coefficient identity?

In terms of hypergeometric series, the sum is $_3F_2(-n, 1+n, 1/2;1,3/2;1)$ and the identity is a special case of Saalschütz's theorem (also called the Pfaff-Saalschütz theorem), one of the standard ...
Ira Gessel's user avatar
  • 16.2k
38 votes
Accepted

Looking for a combinatorial proof for a Catalan identity

By the ballot theorem, $\frac{k}{n} \binom{2n}{n+k}$ is the number of Dyck paths, i.e. $(1,1), (1,-1)$-walks in the quadrant, from the origin to $(2n-1, 2k-1)$. You need to concatenate a pair of those ...
Timothy Budd's user avatar
  • 3,545
38 votes
Accepted

Analogue of Fermat's "little" theorem

Let $$P(x)=(1+x)^a-1-x^a=\sum_{1 \le j \le a-1} \binom{a}{j}x^j.$$ Working in a field $F$ where $|\{\mu \in F: \mu^{p-1}=1\}|=p-1$ (roots of unity of order $p-1$ exist), we have $$ \frac{1}{p-1}\sum_{\...
Ofir Gorodetsky's user avatar
29 votes
Accepted

Are there good bounds on binomial coefficients?

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have $$ \sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}...
kodlu's user avatar
  • 10k
28 votes
Accepted

A combinatorial identity

This is the answer to the first question, I wrote a long answer to Question 2 as a separate answer. Note that $A:=\sum_{k_i>0,k_1+\dots+k_n=K}\frac{K!}{n!k_1!\dots k_n!} \prod k_i^{k_i-1}$ is a ...
Fedor Petrov's user avatar
25 votes

Bernoulli sum meets golden number

Using the integral representation of Bernoulli numbers I obtain formally the integral representation of the double summation $$ \sum_{k=1}^{\infty}\sum_{j=0}^{k}\binom{k}{j}\frac{B_{j+k+1}}{j+k+1}=2\...
Cave Johnson's user avatar
  • 5,282
25 votes

Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$

Denote $h(x,y)=\sum_{i,j\geqslant 0} \binom{i+j}i x^iy^j=\frac1{1-(x+y)}$, $f(x,y)=\sum_{i,j\geqslant 0} \binom{i+j}i^2 x^iy^j$. We want to prove that $2xyf^2(x^2,y^2)$ is an odd (both in $x$ and in $...
Fedor Petrov's user avatar
24 votes
Accepted

A special binomial identity in need of a proof

The $k=j-1$ and $k=-j$ terms cancel, so all that's left is the $k=n$ term.
Ira Gessel's user avatar
  • 16.2k
24 votes
Accepted

Real rootedness of a polynomial

If you have two polynomials $f(x)=a_0+a_1x+\cdots a_mx^m$ and $g(x)=b_0+b_1x+\cdots+b_nx^n$, such that the roots of $f$ are all real, and the roots of $g$ are all real and of the same sign, then the ...
Gjergji Zaimi's user avatar
24 votes

When do binomial coefficients sum to a power of 2?

I doubt this problem has an easy solution. It is clear how it was approached for small fixed $N$. Below I show how it can be addressed for the case of fixed odd $n>1$. When $n>1$ is odd, $S(N,n)$...
Max Alekseyev's user avatar
24 votes
Accepted

When do binomial coefficients sum to a power of 2?

The case $n=2$ was settled by Nagell in 1948 and suspected (?) by Ramanujan in 1913, but in an equivalent form. As John points out in his growing blog post, the $n = 2$ case is a quadratic equation ...
Brian Hopkins's user avatar
20 votes
Accepted

A "quantum" identity: in search of a proof -Part II

Both sides are equal to $\binom{x+y+1}{n}_q$. This enumerates lattice paths in an $n\times (x+y-n+1)$ rectangle, according to the area statistic. We will assume that these paths start at $(0,0)$ and ...
Gjergji Zaimi's user avatar
19 votes
Accepted

An interesting identity: in search of a proof -Part I

This is known as Jensen's identity and dates back to 1902. See here an overview of this identity and related ones, and a proof: https://arxiv.org/abs/1005.2745, a paper by Victor Guo.
Ofir Gorodetsky's user avatar
18 votes

Upper limit on the central binomial coefficient

Noam Elkies notes that there is a quick proof of $$\binom{2n}{n} \leq \frac{4^n}{\sqrt{\pi n}}$$ by writing $$\binom{2n}{n} = \frac{4^n}{\pi} \int_{-\pi/2}^{\pi/2} \cos^{2n} x dx$$ and bounding $\cos^...
David E Speyer's user avatar
18 votes

Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$

When this identity was posted, it struck me as something that ought to have a combinatorial explanation. I have now found one, using a decomposition of NSEW lattice paths: paths in $\mathbb{Z}^2$ ...
Robin Houston's user avatar
17 votes

Integral of power of binomials equal to sum of power of binomials?

I don't know if there is a relation for values of $\ell$ apart from $1$ and $2$ (that would be very interesting, and surprising to me), but here is a unified way to look at what's going on for ...
Lucia's user avatar
  • 43.3k
17 votes

Approximation of sum of the first binomial coefficients for fixed N

One of the more convenient and popular approximations of the sum is $$\frac{2^{nH(\frac{k}{n})}}{\sqrt{8k(1-\frac{k}{n})}} \leq \sum_{i=0}^k\binom{n}{i} \leq 2^{nH(\frac{k}{n})}$$ for $0< k < \...
Yuichiro Fujiwara's user avatar
17 votes
Accepted

Direct combinatorial proof that $2^{2k} = \sum \binom{2i}{i}\binom{2j}{j}$?

Yes, this has an elementary combinatorial interpretation, because $$ {2i \choose i} 2^{-2i} {2j\choose j}2^{-2j} $$ (for $i+j=k$) is the probability that the time of the last return to the starting ...
Christian Remling's user avatar
17 votes

When do binomial coefficients sum to a power of 2?

This is a follow-up to John's answer. Here is the questionable "theorem" from the 2nd (2013) edition of Erickson's book (thanks @spin for the pointer), which in the 1st (1996) edition was ...
Max Alekseyev's user avatar
16 votes

Real rootedness of a polynomial

According to the representation for Jacobi polynomials https://en.wikipedia.org/wiki/Jacobi_polynomials#Alternate_expression_for_real_argument $$ P^{(0,n-m)}_m(x)=\sum_{j=0}^m \binom{m}{j}\binom{n}{j}\...
Cave Johnson's user avatar
  • 5,282
16 votes

Are (55, 165, 495, 1485) and (286, 1716, 10296, 61776) the only geometric sequences of length 4 among non-trivial binomials?

(Partial results.) For the case of integer ratio, there are only two sequences of 4 binomials in geometric progression for which the largest is at most $10^{17}$. Namely, 55,165,495,1485 found by ...
Brendan McKay's user avatar
16 votes
Accepted

binomial coefficients are integers because numerator and denominator form pairs?

The kind of pairing sought does not always exist. Take, for example, $$\binom{8}{4}=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}.$$ The pair of $4$ must be $8$, the pair of $3$ must be $6$, and ...
GH from MO's user avatar
  • 96.9k
15 votes
Accepted

p-adic valuation for multinomial coefficients

Denote the sum of the digits of $n$ in base $b$ by $S(n)$. Then the number of carries when adding $k_1+k_2$ is $$\frac{1}{b-1}\big(S(k_1)+S(k_2)-S(k_1+k_2)\big).$$ This shows that the number of ...
Gjergji Zaimi's user avatar
15 votes
Accepted

A congruence for a product of binomial coefficients?

At first, $$(-1)^k{p-1\choose k}=\frac{(1-p)(2-p)\cdots (k-p)}{1\cdot 2\cdots k}=\left(1-\frac{p}1\right)\left(1-\frac{p}2\right)\cdots \left(1-\frac{p}k\right) \\\equiv 1-pe_1(1,1/2,\ldots,1/k)+p^2 ...
Fedor Petrov's user avatar
14 votes
Accepted

A combinatorial identity involving generalized harmonic numbers

The identity $$ \begin{align} \sum_{s=1}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s }{s+1}H_{s}^{(2)}=\frac{2(-1)^m}{m+1}\sum_{s=1}^m H_{s}^{(2)}. \tag{1} \end{align} $$ is equivalent to the following ...
Cave Johnson's user avatar
  • 5,282
14 votes
Accepted

A curious inequality concerning binomial coefficients

By Cauchy–Bunyakovsky–Schwarz inequality we have $$ \left(\sum \prod_i \frac{\binom{a_i}{b_i}}{\binom{A-a_i}{B-b_i}}\right)\left(\sum\prod_i \binom{a_i}{b_i}\binom{A-a_i}{B-b_i}\right)\geqslant \left(...
Fedor Petrov's user avatar
14 votes

Analogue of Fermat's "little" theorem

Here's a straightforward proof, using generating functions, though it's not as elegant as Ofir's. We have $$ \sum_{a=0}^\infty\binom{a}{j}x^a =\frac{x^j}{(1-x)^{j+1}}. $$ Setting $j=(p-1)k$ and ...
Ira Gessel's user avatar
  • 16.2k
13 votes

Equality with binomials

Let's re-index the sum on the LHS of the problem (for the below convenience) so that $$\frac1s\sum_{k=0}^{s-1}\binom{s+k-1}k(s-k)v^{s-k}(v-1)^k =\frac{v}s\sum_{k=0}^{s-1}\binom{2s}k(s-k)(v-1)^k.$$ Or, ...
T. Amdeberhan's user avatar
13 votes

Approximation of sum of the first binomial coefficients for fixed N

A well-known upper bound, for $k\le N/2$, is $$ \sum_{i=0}^k {N\choose i} \le 2^{N H(k/N)},$$ where $H$ is the binary entropy function $$ H(x) = -x\log_2(x)-(1-x)\log_2(1-x).$$ This bound was ...
Aryeh Kontorovich's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible