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

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

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