The binomial-coefficients tag has no usage guidance, but it has a tag wiki.

**42**

votes

**1**answer

3k views

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

Let $m$ be any positive integer.
$$
P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}{x+j\choose j}{x-1\choose j}{j\choose i}{m\choose i}{i\choose m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}.
$$
Question: $P_m(x)$ always ...

**40**

votes

**2**answers

3k views

### Alternating sum of square roots of binomial coefficients

Let
$$ c_n = \sum_{r=0}^n (-1)^r \sqrt{\binom{n}{r}}. $$
It is clear that $c_n = 0$ if $n$ is odd. Remarkably, it appears that despite the huge positive and negative contributions in the sum ...

**36**

votes

**4**answers

3k views

### Integer-valued factorial ratios

This historical question recalls
Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation
Chebyshev used the factorial ratio sequence
$$
u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)...

**30**

votes

**3**answers

2k views

### A limit involving binomial coefficients?

Experimentation suggests the limit
$$\lim_{n\rightarrow\infty} (-1)^n\sum_{k=1}^n(-1)^k{n\choose k}^{-1/k}=\frac{1}{2}\ .$$
Does somebody have an idea for (a start of) a proof?
Added: There seem to ...

**30**

votes

**3**answers

2k views

### A binomial generalization of the FLT: Bombieri's Napkin Problem

This is an extract from Apéry's biography
(which some of the people have already enjoyed in
this answer).
During a mathematician's dinner in
Kingston, Canada, in 1979, the
conversation turned ...

**23**

votes

**3**answers

3k views

### Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$

I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$.
Some clues that might work (kindly provided by ...

**23**

votes

**1**answer

603 views

### integers which are sums of binomial coefficients: $\sum_i {n \choose k_i}$

Let $n$ be an integer. For $S$ a subset of $\{0,\dots,n\}$, define
$$m(S) = \sum_{k \in S} {n \choose k}.$$
Let $M_n$ be the set of integers of the form $m(S)$ for all sets $S \subset \{0,\dots,n\}$. ...

**19**

votes

**1**answer

1k views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**18**

votes

**1**answer

975 views

### Solutions to $\binom{n}{5} = 2 \binom{m}{5}$

In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says:
On National Public Radio, the Weekend Edition program posed the
following probability problem: Given a certain number of ...

**18**

votes

**0**answers

601 views

### Does $\binom{2n}{n} \equiv 2 \pmod p$ ever hold?

Well, the title does not tell the whole story; the complete question is:
Are there any primes of the form $p=2n(n-1)+1$, with integer $n\ge 1$, such that
$$ \binom{2n}{n} \equiv 2\pmod p ? $$
...

**17**

votes

**1**answer

1k views

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

I have veriﬁed the following double sum is always an integer for $s$ up to $1000$ via Maple.
But I can not prove it. Proofs, hints, or references are all welcome.
Thanks!
$$\sum_{m=s}^{2s}\sum_{k=0}^{...

**16**

votes

**1**answer

756 views

### Are there good bounds on binomial coefficients?

Motivated by the central limit theorem, one expects that
$$\binom{n}{k} \approx \frac{2^n}{\sqrt{\pi n/2}} \exp\left(-\frac{(k-n/2)^2}{n/2}\right).$$
Computations suggest that the ratio of the two ...

**15**

votes

**1**answer

1k views

### Prove that expression is integer

Numerical experiments suggest that
$\binom{2m}{m + k}\cdot\frac{3m - 1 - 2k^2}{2m - 1}$
is integer for all $-m \le k\le +m$. It means that expression evaluation could be implemented very efficiently, ...

**15**

votes

**2**answers

2k views

### Binomial supercongruences: is there any reason for them?

One of the recent questions, in fact
the answer
to it, reminded me about the binomial sequence
$$
a_n=\sum_{k=0}^n{\binom{n}{k}}^2{\binom{n+k}{k}}^2,
\qquad n=0,1,2,\dots,
$$
of the Apéry ...

**13**

votes

**1**answer

386 views

### A combinatorial identity involving generalized harmonic numbers

The $n$-th harmonic number is defined as
$$
H_n=\sum_{k=1}^{n}\frac{1}{k},
$$
and the generalized harmonic numbers are defined by
$$
H_{n}^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}.
$$
Recently, I have found ...

**11**

votes

**5**answers

932 views

### Asymptotics of a Bernoulli-number-like function

Tony Lezard asked me the following question which seemed like it should not be too hard but which I did not immediately see how to answer. Define $f(n,k)$ recursively by $f(1,k) = 1$ and
$$f(n,k) = \...

**10**

votes

**4**answers

1k views

### Rational congruence of binomial coefficient matrices

Skip Garibaldi asks if there is an elementary proof of the following fact that "accidentally" fell out of some high-powered machinery he was working on.
Say that two matrices $A$ and $B$ over the ...

**10**

votes

**2**answers

620 views

### Why are negative sets multisets? (Reference request)

It is easy to establish that
$$
\left(\!\!{n\choose k}\!\!\right)=(-1)^k{-n \choose k},
$$
where the symbol on the left-hand-side counts the number of multisets of $k$ elements from $n$.
On the ...

**9**

votes

**2**answers

1k views

### Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$

I found the following formula in a book without any proof:
$$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$
This does not seem to follow immediately from the basic ...

**9**

votes

**3**answers

2k views

### Showing a matrix is negative definite [formerly Showing a sum is always positive]

For each $d$, I have a matrix $M$ with values
$$
M_{ij} = \begin{cases}
\frac{4ij}{d} - \binom{2d}{d} & i \neq j & \\\\
\frac{4i^2}{d} - \binom{2d}{d} -
\...

**9**

votes

**7**answers

5k views

### Lower bound for sum of binomial coefficients?

Hi! I'm new here. It would be awesome if someone knows a good answer.
Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...

**9**

votes

**2**answers

866 views

### What is $\sum_{i=0}^{n}\binom{n}{i}^3$?

We know that $$\sum_{i=0}^{n}\binom{n}{i}=2^n$$
and that
$$\sum_{i=0}^{n}\binom{n}{i}^2= \binom{2n}{n}$$
what about
$$\sum_{i=0}^{n}\binom{n}{i}^3$$ ?

**9**

votes

**1**answer

385 views

### Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$.
I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$.
(If the answer is ...

**9**

votes

**3**answers

2k views

### Solving a general two-term combinatorial recurrence relation

What is known about explicit (not necessarily closed-form) solutions to the recurrence
$$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$
with initial condition $R_0^0 = 1$ and ...

**8**

votes

**2**answers

608 views

### Zero sum of binomial coefficients

Is there a function $p:\mathbb N\to \{ 1,-1 \} $ and a fixed $N\in \mathbb N$ such that for every $n \geq N$ we get:
$\sum _{i=0} ^{n} p(i)\binom {n}{i}=0$
?
Obviously $p(i)=(-1)^i$ works for $N=1$...

**8**

votes

**1**answer

502 views

### What is $\lim_{n\to\infty} \displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\left(4^{-k}\binom{2k}{k}\right)^{\frac{2n}{\log_2{n}}}\,?$

What is $$\lim_{n\to\infty} \displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\left(4^{-k}\binom{2k}{k}\right)^{\frac{2n}{\log_2{n}}}\,?$$

**8**

votes

**0**answers

539 views

### Does anyone know this sequence of polynomials?

A referee on a paper of mine showed me the following recurrence for polynomials $P_{n,k}\in\mathbb Q[q,q^{-1}]$ for $n\geq 0$ and $0\leq k\leq n/2$.
\begin{align}
P_{0,0}&=1\\
\text{for $n\geq 1$}...

**7**

votes

**6**answers

883 views

### Binomial coefficient identity

It seems to be nontrivial (to me) to show that the following identity holds:
$$ \binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} \frac {n(-1)^k}{n+k} = 1. $$
This quantity is related to the volume of the ...

**7**

votes

**3**answers

656 views

### Combinatorial identities

I have computational evidence that
$$\sum_{k=0}^n \binom{4n+1}{k} \cdot \binom{3n-k}{2n}= 2^{2n+1}\cdot \binom{2n-1}{n}$$
but I cannot prove it. I tried by induction, but it seems hard. Does anyone ...

**7**

votes

**3**answers

874 views

### Binomial coefficient in Andrews' partition book

First of all, i think MathOverflow is a very great community to discuss math, either basic or advanced, and i'm glad to participate here. It's my first post, so i'm sorry if i did anything wrong, and ...

**7**

votes

**1**answer

378 views

### Quest for a human proof of a $q-$binomial identity

Let $$f(n,k) = \sum\limits_{j = - k}^k {{{( - 1)}^{k - j}}}
\binom{n-j}{k-j}\binom{n+j}{k+j}.$$
Then $f(n,k)=\binom{n}{k}$
because it satisfies $f(n,k)=f(n-1,k)+f(n-1,k-1)$ and the obvious ...

**7**

votes

**0**answers

327 views

### Polynomials with presumably positive coefficients

The $q$-Pochhammer symbol
$(q) _ 0:=1$ and $(q) _ n:=\prod _ {j=1}^n (1-q^j)$ for $n > 0$ is clearly a polynomial in $q$ which has both positive and negative coefficients when $n>0$.
The $q$-...

**7**

votes

**0**answers

788 views

### Inverse of a matrix with binomial coefficients

Let $a(n,k)=(-1)^k {{2n-k}\choose k}$ for $0 \le k \le n$ and $a(n,k)=0$ else. Then it is known (cf. OEIS A005439 and A098435) that the first column of the inverse matrix of $(a(i,j))_{i,j\ge0}$ is ...

**6**

votes

**3**answers

1k views

### Multiplicative Convolution for Binomial Coefficients

I know Vandermonde's convolution for binomial coefficients:
$$\sum_{j=0...k} \binom{n}{j} \binom{m}{k-j} = \binom{n+m}{k}$$
Is there a similar multiplicative convolution? More precisely, is there a ...

**6**

votes

**1**answer

691 views

### Sums of binomials with even coefficients

While looking for a closed form of a expression I worked myself to a formula that resembles the Vandermonde convolution, but is summed over even binomial coefficients only.
$\sum_{k=0}^n\sum_{l=0}^n{...

**6**

votes

**4**answers

697 views

### Maximum value of the binomial coefficient as a polynomial

What is the maximum (absolute) value of the binomial coefficient
$\begin{pmatrix}x \\ k\end{pmatrix} = \frac{1}{k!}x(x-1)(x-2)\dotsb(x-k+1)$
for real $x$ in the interval $0 \leq x \leq k-1$?

**6**

votes

**1**answer

838 views

### Divisibility of a binomial coefficient by $p^2$ — current status

While skimming the book Concrete Mathematics, (edit: first edition) I came across the following problem, which is listed there as a Research Problem: (Chapter 5, Exercise 96)
Is ${2n \choose n}$ ...

**6**

votes

**3**answers

520 views

### Is there a closed formula for the generating function of some trinomial coefficients?

We learn in calculus how to obtain a sum of binomial coefficients $\frac{(2d)!}{(d!)^2}$ in terms of a generating function
$\sum_{d \geq 0} \frac{(2d)!}{(d!)^2} x^d$
by the Taylor series of $(1-4x)^...

**6**

votes

**2**answers

570 views

### Asymptotic difference between a function and its “binomial average”

(I posted this question on Math.SE a few weeks ago. I got a few comments, but nothing definite, and so I thought I would try MO.)
The origin of this question is the identity
$$\sum_{k=0}^n \binom{n}{...

**6**

votes

**2**answers

771 views

### Closed form or/and asymptotics of a hypergeometric sum

Dear mathematicians,
I am a computer scientist wandering in the deep sea of combinatorics and asymptotics to pursue a recent interest in average case analysis of algorithms. In doing so, I designed ...

**6**

votes

**1**answer

598 views

### Double sum involving binomial coefficients

I came across a sum of binomial coefficients while trying to solve a problem involving $SU(2)$ group integrals. I am not able to solve it, nor I found a similar identity in the literature. I would ...

**5**

votes

**2**answers

539 views

### Interpolating a sum of binomial coefficients using a sin function

While studying a problem about orthogonal polynomials I encountered the following
expressions
\begin{equation}
f(n)=\sum_{k=0}^{n}(-1)^k\binom{n+k}{2k} \frac{1}{k+1}\binom{2k}{k}
\end{equation}
and
\...

**5**

votes

**1**answer

457 views

### Elementary proof for identity involving sums of binomials

Is there an elementary proof of this identity?
$$n + 1 - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+1-k}}{n^{n}} =1 + \sum_{k=1}^n \frac{n!}{(n-k)!n^k}\;?$$
The term on the right is the ...

**5**

votes

**2**answers

384 views

### Can you simplify (or approximate) $\sum_{n=0}^{N-1} \binom{N-1}n \frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?

Let $\binom x y$ be the binomial coefficient. I am trying to get a better understanding of the sum
$$
f(N,\lambda)=\sum_{n=0}^{N-1}\binom{N-1}n\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}
$$
as a ...

**5**

votes

**2**answers

316 views

### Combinatorial identity and Fuss-Catalan numbers

I would like to show that
$$
\lim_{N\to\infty}\frac{1}{N^{np+1}}\frac1{p!}\sum_{j=0}^{p-1}(-1)^j\binom{p-1}{j}
\left(\frac{\Gamma(N+p-j)}{\Gamma(N-j)}\right)^{n+1}
=\frac1{np+1}\binom{(n+1)p}{p},
$$
...

**5**

votes

**1**answer

214 views

### Estimate of incomplete binomial integral

Let $0\le k \le n$. Prove that
$$
n\binom{n}{k}\int_{0}^{\frac{k}{n+1}}t^k(1-t)^{n-k}\,dt \le 1/2.
$$
As far as I know
1) it is proved for $\frac{k}{n+1}\le 1/2$ and
2) not proved for $1/2 <\frac{...

**5**

votes

**0**answers

142 views

### An inequality concerning non-negative integer matrices with constant row and column sums

[I posted this question on math.stackexchange a few weeks back, but no luck there so far: http://math.stackexchange.com/questions/1095659/an-inequality-concerning-non-negative-integer-matrices-with-...

**4**

votes

**3**answers

394 views

### On a theorem of Hensel about congruence of binomial coefficient

In the paper Binomial coefficients modulo prime powers, Andrew Granville stated the following theorem:
Let $n, m$ and $r=n-m$ be three given positive integer and $p^k$ is the exact power of $p$ ...

**4**

votes

**1**answer

353 views

### Product of central binomial coefficients

I have a question about an equality involving products of central binomial coefficients. If $x_1,...,x_n$ and $y_1,...,y_n$ are positive integers, with $\sum_i x_i = \sum_i y_i$ and
$$ \binom{2x_1}{...

**4**

votes

**3**answers

162 views

### Asymptotic expression for $j$ which satisfies $\binom{n}{j}/j! \sim k$ as $n\to\infty$

Suppose $k>0$ is some fixed constant, and $n$ is a positive integer tending to infinity. Find $j\equiv j(n,k)$ such that
$$ \frac{\binom{n}{j}}{j!} \sim k. $$
The asymptotic expression for $(n!)^...