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

- 14.4k

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

- 14.4k

43
votes

Accepted

### Prove that expression is integer

It equals
$$
\binom{2m}{m+k}\frac{3m-1-2k^2}{2m-1}=-(m-1)\binom{2m}{m+k}+4m\binom{2m-2}{m+k-1}.
$$
I got it by expanding $3m-1-2k^2=2(m^2-k^2)-(2m^2-3m+1)=2(m-k)(m+k)-(2m-1)(m-1)$.

- 90.9k

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

- 3,335

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

- 9,789

35
votes

Accepted

### How to prove this polynomial always has integer values at all integers?

$$P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}\binom{x+j}{ j}\binom{x-1}{ j}\binom{j}{ i}\binom{m}{ i}\binom{i}{ m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}.$$
Our task is to show it takes integer values on integers.
...

- 3,216

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

- 90.9k

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

- 8,981

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

- 4,710

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

- 90.9k

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

- 82.6k

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

- 27.4k

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

- 3,256

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

- 14.4k

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

- 82.6k

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.

- 9,789

17
votes

Accepted

### How to prove that the following double sum is always an integer？

Here is an attempt at an answer. We assume that the recurrence from my comment above holds [with a small correction] (a proof was obtained by Kevin using Zeilberger's algorithm, see the comment below):...

- 10.7k

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

- 2,616

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

- 27.4k

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

- 42.7k

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

- 3,622

16
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.5k

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

- 4,710

15
votes

### Sum of 'the first k' binomial coefficients for fixed $N$

Here's one from an old paper of mine. It has the property of being precise all the way from the middle to the end.
Define
$$ Y(x) = e^{x^2/2}\int_x^\infty e^{-t^2/2}dt. $$
Define $x=(2k-n)/\sqrt{n}$. ...

- 34.8k

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

- 82.6k

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

- 4,710

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

- 90.9k

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

- 14.4k

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

- 39.1k

13
votes

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

Oh no, I was too slow... sorry for the double reference. This is Jensen's identity. It first appeared (in a slightly modified form) in: Jensen, Sur une identité d'Abel et sur d'autres formules ...

- 1,374

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

#### Related Tags

binomial-coefficients × 369co.combinatorics × 234

nt.number-theory × 81

sequences-and-series × 48

asymptotics × 34

reference-request × 30

combinatorial-identities × 30

pr.probability × 15

polynomials × 14

enumerative-combinatorics × 12

hypergeometric-functions × 12

q-analogs × 12

real-analysis × 11

inequalities × 11

limits-and-convergence × 11

congruences × 11

analytic-number-theory × 10

prime-numbers × 10

stirling-numbers × 10

additive-combinatorics × 9

generating-functions × 9

recurrences × 9

ca.classical-analysis-and-odes × 8

closed-form-expressions × 8

special-functions × 7