Questions tagged [binomial-coefficients]

For questions that explicitly reference the binomial coefficients, Pascal's Triangle, and Binomial identities.

Filter by
Sorted by
Tagged with
118 votes
15 answers
97k views

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

I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other ...
mathy's user avatar
  • 1,258
20 votes
8 answers
12k 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 $\...
user13006's user avatar
  • 233
12 votes
4 answers
5k views

Estimating a partial sum of weighted binomial coefficients

There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$: $$ \sum_{k=0}^{\alpha n}\...
bandini's user avatar
  • 491
45 votes
5 answers
5k 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)...
Wadim Zudilin's user avatar
23 votes
1 answer
6k 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 ...
Kevin O'Bryant's user avatar
10 votes
1 answer
706 views

What is known about sums of the form $\sum_{n=2}^{\infty}[\zeta(n)-1]^{p} $?

A fair bit is known about rational zeta series. This includes identities like $$ \sum_{n=2}^{\infty} [\zeta(n) -1] = 1 . $$ Many more identities can be found in articles by e.g. Borwein and Adamchik &...
Max Muller's user avatar
  • 4,485
43 votes
2 answers
6k 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 ...
Mark Wildon's user avatar
  • 10.8k
26 votes
3 answers
4k 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 ...
Alexandra Seceleanu's user avatar
4 votes
2 answers
2k 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, $a_\...
Liss's user avatar
  • 145
35 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 ...
Wadim Zudilin's user avatar
18 votes
3 answers
858 views

$\prod_k(x\pm k)$ in binomial basis?

Let $x$ be an indeterminate and $n$ a non-negative integer. Question. The following seems to be true. Is it? $$x\prod_{k=1}^n(k^2-x^2)=\frac1{4^n}\sum_{m=0}^n\binom{n-x}m\binom{n+x}{n-m}(x+2m-n)^...
T. Amdeberhan's user avatar
9 votes
1 answer
387 views

Eigenvalues of a matrix with binomial entries

I am trying to determine the eigenvalues and eigenvectors of the following matrix: $$M_{ij} = 4^{-j}\binom{2j}{i}$$ where it is understood that the binomial coefficient $\binom{m}{k}$ is zero if $k&...
valle's user avatar
  • 864
6 votes
1 answer
827 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 $ \...
Shir's user avatar
  • 327
1 vote
1 answer
215 views

Worpitzky-like identities?

Let $$r_k(x)=\prod_{j=1}^k {(\frac{x+j}{j}})^{\min(j,k-j)}.$$ Computations suggest that $$r_{2k}(x)=\sum_{j=0}^{(k-1)^2}a(2k,j)\binom{k^2+x-j}{k^2}$$ and $$r_{2k+1}(x)=\sum_{j=0}^{k^2-k}a(2k+1,j)\...
Johann Cigler's user avatar
54 votes
4 answers
4k views

When do binomial coefficients sum to a power of 2?

Define the function $$S(N, n) = \sum_{k=0}^n \binom{N}{k}.$$ For what values of $N$ and $n$ does this function equal a power of 2? There are three classes of solutions: $n = 0$ or $n = N$, $N$ is odd ...
John D. Cook's user avatar
  • 5,147
39 votes
3 answers
5k views

A limit involving binomial coefficients: $\lim_{n\to\infty} (-1)^n\sum_{k=1}^n(-1)^k{n\choose k}^{-1/k}=\frac12$?

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 ...
Roland Bacher's user avatar
31 votes
3 answers
2k views

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

In my research, I found this identity and as I experienced, it's surely right. But I can't give a proof for it. Could someone help me? This is the identity: let $a$ and $b$ be two positive integers; ...
ken's user avatar
  • 311
27 votes
2 answers
1k views

Some binomial coefficient determinants

It is well known that for $n>0$ $$d(n)=\det\left(\binom{2i+2j+1}{i+j}\right)_{i,j=0}^{n-1}=1.$$ Computer experiments suggest that more generally $$d(n,k)=\det\left(\binom{2i+2j+2k+1}{i+j}\right)_{i,...
Johann Cigler's user avatar
26 votes
1 answer
1k 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 ...
Nick Matteo's user avatar
21 votes
2 answers
1k views

Real rootedness of a polynomial

Let's consider $m$ and $n$ arbitrary positive integers, with $m\leq n$, and the polynomial given by: $$ P_{m,n}(t) := \sum_{j=0}^m \binom{m}{j}\binom{n}{j} t^j$$ I've found with Sage that for every $...
Luis Ferroni's user avatar
  • 1,879
21 votes
2 answers
1k views

Direct combinatorial proof that $2^{2k} = \sum \binom{2i}{i}\binom{2j}{j}$?

In a purely algebraic way, I've just stumbled onto the fact that $$2^{2k} = \sum_{i+j=k} \binom{2i}{i}\binom{2j}{j},$$ i.e. that the self-convolution of the sequence $\binom{2k}{k}$ is the sequence $...
benblumsmith's user avatar
  • 2,831
20 votes
7 answers
5k views

Upper limit on the central binomial coefficient

What is the tightest upper bound we can establish on the central binomial coefficients $ 2n \choose n$ ? I just tried to proceed a bit, like this: $$ n! > n^{\frac{n}{2}} $$ for all $ n>2 $. ...
RandomStudent's user avatar
20 votes
1 answer
2k views

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

I have verified 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}^{...
Chitsai Liu's user avatar
  • 2,153
20 votes
3 answers
3k views

a sum with binomial coefficients

Let integers $n,k$ satisfy $0 \le k \le n$. We desire proof that $$ {n\choose k} = \sum {n\choose a}(-1)^a\;{-k\choose b}(-1)^b\;{-(n-k)\choose c}(-1)^c \tag{$*$}$$ where the (finite) sum is over all ...
Gerald Edgar's user avatar
  • 40.2k
19 votes
2 answers
559 views

Eigenvalues and eigenvectors of the matrix with entries $\dbinom{n+1}{2j-i}$ for $i, j = 1, 2, \ldots, n$

Let $n$ be a nonnegative integer, and let $B$ be the $n \times n$-matrix (over the rational numbers) whose $\left(i, j\right)$-th entry is $\dbinom{n+1}{2j-i}$ for all $i, j \in \left\{ 1, 2, \ldots, ...
darij grinberg's user avatar
18 votes
2 answers
3k 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 ...
Wadim Zudilin's user avatar
16 votes
2 answers
593 views

3-adic valuation of a sum involving binomial coefficients

Let $$a(n) = \sum_{0 \leq k \leq n} {n \choose k}{{n+k} \choose k},$$ and define $b(n) = \nu_3 \bigl(a(n)\bigr)$, where $\nu_3$ is the $3$-adic valuation. About twenty years ago or so, I discovered (...
Jeffrey Shallit's user avatar
14 votes
2 answers
784 views

Integral of power of binomials equal to sum of power of binomials?

Inspired by this MO question about integrating binomial coefficients and the answers, I was wondering whether integrating powers of binomial coefficients also relates to the respective sums. And ...
Andreas Rüdinger's user avatar
13 votes
2 answers
2k 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 ...
mathlove's user avatar
  • 4,727
13 votes
3 answers
1k views

Does the set $\{\binom x3+\binom y3+\binom z3:\ x,y,z\in\mathbb Z\}$ contain all integers?

The Gauss-Legendre theorem on sums of three squares states that $$\{x^2+y^2+z^2:\ x,y,z\in\mathbb Z\}=\mathbb N\setminus\{4^k(8m+7):\ k,m\in\mathbb N\},$$ where $\mathbb N=\{0,1,2,\ldots\}$. It is ...
Zhi-Wei Sun's user avatar
  • 14.4k
13 votes
5 answers
2k views

Looking for a combinatorial proof for a Catalan identity

Let $C_n=\frac1{n+1}\binom{2n}n$ be the familiar Catalan numbers. QUESTION. Is there a combinatorial or conceptual justification for this identity? $$\sum_{k=1}^n\left[\frac{k}n\binom{2n}{n-k}\right]^...
T. Amdeberhan's user avatar
13 votes
5 answers
1k 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) = \...
Timothy Chow's user avatar
  • 78.1k
12 votes
2 answers
1k views

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

I like the following binomial identity in that the RHS extracts the indeterminate $w$ from the LHS. Question. Can you show that $$\sum_{k=0}^n\binom{x+kw}k\binom{y-kw}{n-k}=\sum_{k=0}^n\binom{x+y-...
T. Amdeberhan's user avatar
12 votes
1 answer
255 views

Total positivity of $q$-Pascal matrix?

A matrix of real numbers is called totally positive if all its minors are non-negative. A well-known example is the Pascal matrix $(\binom{i}{j})$. Is it true that the minors of the $q$-Pascal matrix ...
Johann Cigler's user avatar
12 votes
5 answers
810 views

A divisibility of q-binomial coefficients combinatorially

Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient ${a+b \choose a}$. I know how to prove this combinatorially - for example after choosing an ordered set ...
Peter McNamara's user avatar
10 votes
3 answers
479 views

Equality with binomials

I am reading a paper and I am trying to understand an equality which is given without proof: $$\sum_{k=1}^s\binom{2s-k}{s}\frac{k}{2s-k}v^k(v-1)^{s-k}=v\sum_{k=0}^{s-1}\binom{2s}{k}\frac{s-k}{s}(v-1)^{...
LuHell's user avatar
  • 333
10 votes
4 answers
1k 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 ...
Guilherme's user avatar
  • 103
9 votes
2 answers
778 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}{...
Mike Spivey's user avatar
  • 3,253
9 votes
1 answer
389 views

Series for $\frac{\log m}{\pi}$ with summands involving harmonic numbers

The classical rational Ramanujan-type series for $1/\pi$ have the following four forms: \begin{align}\sum_{k=0}^\infty(ak+b)\frac{\binom{2k}k^3}{m^k}&=\frac{c}{\pi},\label{1}\tag{1} \\\sum_{k=0}^\...
Zhi-Wei Sun's user avatar
  • 14.4k
9 votes
3 answers
1k 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$...
Shir's user avatar
  • 327
8 votes
2 answers
1k 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 \...
Stefano Capparelli's user avatar
7 votes
0 answers
330 views

Do generalizations of the identity $\sum_{n=k+2}^{\infty} \binom{n-1}{k} (\zeta(n) -1) = 1 $ exist?

On p. 263 of Borwein's paper entitled “Computational Strategies for the Riemann zeta function”, the following identity is stated: $$\sum_{n=k+2}^{\infty} \binom{n-1}{k} (\zeta(n) -1) =1 . \qquad \...
Max Muller's user avatar
  • 4,485
7 votes
1 answer
964 views

Bounding the probability that two binomials are equal

Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question. Let $B_{n,p}$ denote the usual binomial random ...
Pat Devlin's user avatar
  • 2,660
7 votes
9 answers
2k 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 ...
hkju's user avatar
  • 245
6 votes
0 answers
187 views

Looking for a combinatorial proof for an identity involving $q$-Catalan triangles

Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Following my earlier post on MO, one fine colleague asked me if there is a $q$-analogue of the identity formed by the so-called Shapiro's ...
T. Amdeberhan's user avatar
6 votes
3 answers
728 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)^...
user20592's user avatar
5 votes
1 answer
667 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 ...
ELW's user avatar
  • 83
5 votes
4 answers
817 views

Limit of a sum with binomial coefficients

Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$ $$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ $$C_k = \frac{\sum_{i=1}^k(...
macat's user avatar
  • 145
5 votes
2 answers
547 views

Is there a simple proof of the following binomial Identity (part 2)?

This is a related question to the one I posted on MO earlier: Is there a simple proof of the following Identity for $\sum_{k=m-1}^l(-1)^{k+m}\frac{k+2}{k+1}{\binom l k}\binom{k+1}m$? It arose in the ...
Brendan Guilfoyle's user avatar
5 votes
2 answers
368 views

Asymptotic rate for $\sum\binom{n}k^{-1}$

This MO question prompted me to ask: What is the second order asymptotic growth/decay rate for the sum $$\sum_{k=0}^n\frac1{\binom{n}k}$$ as $n\rightarrow\infty$?
T. Amdeberhan's user avatar