The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
717 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
727 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
166 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
481 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
669 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
519 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
598 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
227 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
587 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
735 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
928 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
3k 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
622 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
523 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
728 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}$ ...
2
votes
2answers
540 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
2answers
937 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
3k 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
570 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
1k 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 ...
31
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 $$ ...
12
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
829 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
497 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 ...