The binomial-coefficients tag has no wiki summary.

**37**

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

**32**

votes

**4**answers

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

**28**

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

**28**

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

**1**answer

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

**17**

votes

**3**answers

2k views

### Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$

Hello.
I have been trying very hard to show that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ and could not quite get anywhere. This inequality has been verified by computer ...

**17**

votes

**1**answer

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

**16**

votes

**0**answers

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

**14**

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

**13**

votes

**1**answer

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

**11**

votes

**5**answers

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

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

4k 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

**3**answers

1k 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

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

**8**

votes

**1**answer

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

**7**

votes

**2**answers

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

**7**

votes

**3**answers

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

**6**

votes

**3**answers

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

**6**

votes

**3**answers

837 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

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

**6**

votes

**1**answer

765 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

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

**6**

votes

**2**answers

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

**6**

votes

**2**answers

699 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

**2**answers

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

**6**

votes

**0**answers

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

**6**

votes

**0**answers

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

**6**

votes

**0**answers

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

**5**

votes

**6**answers

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

**5**

votes

**2**answers

455 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

403 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

**4**answers

368 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$?

**4**

votes

**1**answer

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

**4**

votes

**1**answer

491 views

### What is the degree of a symmetric boolean function?

(previous title " Zero sum of binomials coefficients - a stronger version ")
This is a stronger version of another question.
Is there an $N\in \mathbb N$ and a sequence of non-constant functions $ ...

**4**

votes

**1**answer

252 views

### Summing ratio of ratio of partial sums of binomial coefficients

I would like to approximate the following when $n \gg k$.
$\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$
The formula can be re-written ...

**4**

votes

**1**answer

2k views

### sum calculation

I would like to calculate, or bound from above, the following sum
$$
\sum_{i=0}^n(n-2i)^p{p \choose i},
$$
here $p\geq 2$.
Any references are very welcome.
Thank you.

**4**

votes

**0**answers

144 views

### How find this binomial-coefficients sum $\sum_{k_{1}+k_{2}+\cdots+k_{d}=n}\binom{n}{k_{1},k_{2},\cdots,k_{d}}^2$ [duplicate]

Assmue that $d$ is give postive integer numbers,and
$$(x_{1}+x_{2}+\cdots+x_{d})^n=\sum_{k_{1}+\cdots+k_{d}=n} \binom{n}{k_{1},k_{2},\cdots,k_{d}}x^{k_{1}}_{1}x^{k_{2}}_{2}\cdots ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

230 views

### Recurrence relation for trinomial Apery numbers

It is well known (Beukers 1987) that the Apery numbers $$A_n\equiv A_n^{(2)}=\sum\limits_{k=0}^n\binom{n}{k}^2\binom{n+k}{k}^2$$ satisfy the fancy recurrence relation
...

**4**

votes

**0**answers

73 views

### alternating sum with Barnes G functions

Let $B(n)=(n-2)!(n-3)!\cdots 1!$ denote the Barnes G-function.
I am pretty sure that
$$
\sum_{m=0}^{k^2-1}
(-1)^m\binom{k^2-1}m
\frac{G(k+n-m+1)}{G(n-m+1)G(k+1)(k^2)!}
= n-2k^2-2k
$$ when $k$ is ...

**4**

votes

**0**answers

245 views

### A coincidence concerning Fermat primes, binomial sums, and eta quotients?

Let $w_k$ be a primitive k th root of unity, where k is a power of 2. In response to a question, Robert Israel gave the solution,
$$\sum_{n=0}^\infty \frac{(-1)^n}{\binom{kn}{kn/2}} = ...

**3**

votes

**2**answers

4k views

### Combinatorial proof of a recurrence for the Catalan numbers

I would like to ask whether there is a combinatorial proof of the following recurrence relation for Catalan numbers:
$$
C_{n+1}=\frac{4n+2}{n+2} C_n.
$$
Thanks!~

**3**

votes

**1**answer

637 views

### Yet another sum involving binomial coefficients

Let $k,p$ be positive integers. Is there a closed form for the sums
$$\sum_{i=0}^{p} \binom{k}{i} \binom{k+p-i}{p-i}\text{, or}$$
$$\sum_{i=0}^{p} \binom{k-1}{i} \binom{k+p-i}{p-i}\text{?}$$
...

**3**

votes

**1**answer

518 views

### Estimate on sum of squares of multinomial coefficients

I am interested in approximating the sum of the squares of the multinomial coefficients, i.e.
$a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$
or more general,
...

**3**

votes

**3**answers

389 views

### Estimating a sum involving binomial coefficients [refined]

Having some work done, here is a refined version of my initial question.
For integer $m>0$ and $0\le q\le m$, consider the sum
$$ S(m,q) = \sum_{i=0}^{m-q} \binom{m}{i} \binom{m-i}{q}^2. $$
I ...

**3**

votes

**1**answer

244 views

### Limit of sum of binomials

I'm trying to calculate the limit for the sum of binomial coefficients:
$$S_{n}=\sum_{i=1}^n \left(\frac{{n \choose i}}{2^{in}}\sum_{j=0}^i {i \choose j}^{n+1} \right).$$
Numerically it seems to ...

**3**

votes

**2**answers

642 views

### How to restore the original formula from a binomial-like expansion?

I encountered with a recursive formula of the following kind:
$$A(0,x)=1$$
$$A(n,x)= \sum _{j=0}^{n-1} \binom{n-1}{j} A(n-j-1,x) \sum _{k=0}^{x-1} A(j,k)$$
The sum terms can be re-arranged so to ...

**3**

votes

**2**answers

185 views

### A sum related to the Johnson association scheme

Hi everyone,
In the process of studying a problem in the Johnson association scheme I came across the following sum:
$$\sum_{k\geq 0}(-1)^k\binom{n}{k}\binom{a-k}{a-b}\binom{c+k}{b}.$$
All the ...