The tag has no wiki summary.

learn more… | top users | synonyms

36
votes
2answers
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
4answers
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
3answers
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
3answers
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
1answer
534 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
3answers
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
1answer
821 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 ...
14
votes
0answers
350 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 ? $$ ...
13
votes
1answer
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
5answers
844 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
4answers
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
3answers
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
3answers
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
2answers
535 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
7answers
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 ...
8
votes
1answer
442 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
2answers
875 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
3answers
757 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
3answers
541 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
3answers
799 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
1answer
601 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
1answer
745 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
3answers
450 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
2answers
532 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
2answers
684 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
2answers
459 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
0answers
302 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
0answers
455 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
0answers
649 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
2answers
437 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
1answer
397 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
4answers
339 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
1answer
330 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
1answer
487 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
1answer
233 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
1answer
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
0answers
266 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
0answers
226 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
0answers
67 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
0answers
242 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
2answers
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
1answer
620 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
3answers
355 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
1answer
227 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
2answers
178 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 ...
3
votes
2answers
618 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 ...
2
votes
3answers
583 views

An identity involving sum of probably binomial coefficients

How could I prove that $$\sum _{m=v}^n \left(\left(\prod _{k=v}^{m-1} \frac{k^2}{m^2-k^2}\right)\left(\prod _{k=m+1}^n \frac{k^2}{k^2-m^2}\right)(-1)^{m-v}\right)=1$$ or, simplified, $$\sum _{m=v}^n ...
2
votes
3answers
1k 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 ...
2
votes
2answers
439 views

Sum involving binomial coefficients

I have the following sum $\sum_{j=1}^K {K \choose j} (-1)^{j+1}/j$. Now I can write this as the integral $\int_{-1}^0 \frac{(1+x)^K - 1}{x} dx$. However, I wonder whether there is a closed form ...
2
votes
3answers
503 views

Variant of binomial coefficients

I've recently come across a variant of the binomial polynomials, and I'm curious if anyone has seen these before. If so, I'd love a reference, a name, etc. First recall the following. If z is a ...