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_{\...

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 ...

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 ...

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_{\...

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}...

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 ...

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\...

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 $...

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.

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 ...

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)$...

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 ...

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 ...

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.

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^...

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$ ...

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 ...

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 < \...

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 ...

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 ...

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}\...

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 ...

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 ...

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 ...

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 ...

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 ...

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(...

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 ...

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, ...

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 ...

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

#### Related Tags

binomial-coefficients × 405co.combinatorics × 252

nt.number-theory × 95

sequences-and-series × 53

combinatorial-identities × 37

asymptotics × 36

reference-request × 33

polynomials × 16

pr.probability × 15

enumerative-combinatorics × 14

congruences × 14

q-analogs × 13

real-analysis × 12

inequalities × 12

limits-and-convergence × 12

hypergeometric-functions × 12

analytic-number-theory × 11

prime-numbers × 11

additive-combinatorics × 10

recurrences × 10

stirling-numbers × 10

ca.classical-analysis-and-odes × 9

generating-functions × 9

catalan-numbers × 9

closed-form-expressions × 8