The tag has no wiki summary.

learn more… | top users | synonyms

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 ...
0
votes
0answers
179 views

Asymtotic Complexity Analysis using logarithms and binomial coefficients

On page 11 of "Smaller decoding exponents: ball-collision decoding" by Berstein et.al. they have the formula \begin{equation}\lim_{n \rightarrow \infty} ...
2
votes
1answer
290 views

(Asymptotics of) Sum involving alternating sign Chu-Vandermonde

While considering eigenvalues of a certain Cayley graph, I came across the following sum: $$\sum_{r=0}^{d}\sum_{i=0}^{r} (-1)^{i} \binom{w}{i}\binom{n-w}{r-i}$$ where $d$, $w$, and $n$, are all ...
2
votes
2answers
884 views

alternating sum of binomial coefficients

I would like to know a closed formula for $\sum_{j=0}^{p-n } (-1)^j\binom{n^2}{p-n-j} \binom{n+j-1}j\binom{2n+j}{n+j+1}$, especially in the case $p$ is near $n^2/2$. Similarly, I would like a closed ...
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 ...
6
votes
0answers
303 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
3answers
456 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 ...
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 ...
6
votes
0answers
458 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$. ...
1
vote
1answer
308 views

Limit of an infinite series, related to (generalised Newton's) binomial expansion

How to calculate the infinite sum of the following series, related to binomial expansion for rational number, $r$: ...
6
votes
1answer
609 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. ...
0
votes
2answers
923 views

non negative integer solutions : Diophantine Equations [closed]

I want to know the exact number of non-negative integer solutions of a1x1+a2x2+...akxk = n ... I know that it is the co-efficient of x^n in (1-x^a1)^-1 * (1-x^a2)^-1 * ... (1-x^ak)^-1 ... but whats ...
0
votes
1answer
773 views

How to calculate such sum of product of binomial coefficient?

..I wonder if the following formula can be calculated? $ \sum_{k=0}^m {m \choose k} {2k \choose n} $
7
votes
3answers
764 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 ...
0
votes
0answers
171 views

$q$-binomials in terms of ordinary binomials

Is there a known identity that expresses the $q$-binomial coefficients (also known as Gaussian binomial coefficients) in terms of the (ordinary) binomial coefficients?
4
votes
1answer
488 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 $ ...
6
votes
2answers
690 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 ...
8
votes
2answers
542 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 ...
3
votes
1answer
626 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{?}$$ ...
2
votes
1answer
235 views

Bounding a hypergeometric sum

Is there a general method for finding upper bounds of hypergeometric sums? The sum in particular I am trying to bound is $\sum_{j=1}^{k}\binom{k-1}{j-1}\binom{n-k-1}{j-1}4^{k-j}$. This is a ...
0
votes
2answers
646 views

Cosine of a Partial Sum

Does anyone know of a closed formula for $cos(\displaystyle\sum_{n=0}^m a_{n})$? I've seen formulas for $cos(\displaystyle\sum_{n=0}^\infty a_{n})$ and $tan(\displaystyle\sum_{n=0}^m a_{n})$, but the ...
6
votes
3answers
810 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 ...
0
votes
1answer
1k views

The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that: the product of non-adjacent vertices is constant. the greatest common ...
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 ...
6
votes
0answers
663 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
2answers
534 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
1answer
755 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}$ ...
3
votes
2answers
630 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 ...
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 ...
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!~
2
votes
1answer
624 views

Partial sums of the Chu--Vandermonde identity

I am interested in finding a lower bound of the sum: $$\sum_{i=0}^d \left(\genfrac{}{}{0pt}{}{n}{i}\right) \left(\genfrac{}{}{0pt}{}{m}{k-i}\right)$$ when $d < k$ (and assuming both $n\geq k$, ...
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 ...
1
vote
2answers
2k views

bound for binomial coefficients

How can one show $\displaystyle\frac{(m+n-1)!}{m ! (n-1)!}\leq \left[\frac{e (m+n-1)}{n}\right]^{n-1}$ ?
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 ...
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 ...
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 $$ ...
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 ...
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} - ...
11
votes
5answers
848 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) = ...
2
votes
3answers
506 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 ...