The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
0answers
81 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
1answer
285 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 ...
2
votes
0answers
228 views

Weighted sum of ratio of partial sum of binomial coefficients

I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$, $\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
2
votes
0answers
125 views

Resources on Wolstenholme's theorem

In Wikipedia entry on Wolstenholme's theorem, it says ...
1
vote
0answers
387 views

Another identity involving sums of (alternating) binomial coefficients.

I have derived two different solutions to the same problem involving computing the expected time to find $k$ swaps when collecting coupons. However to me the two sums, although apparently numerically ...
3
votes
1answer
617 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, ...
18
votes
1answer
910 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 ...
5
votes
1answer
426 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 ...
1
vote
0answers
88 views

binomial transform, Hurwitz zeta function

For $j,n\in\mathbb Z_+$, let $$ L_{j,n}^{(t)}= \sum_{m=0}^{n} \Bigl(-\frac 12\Bigr)^{n-m}{n\choose m}{m+j+1\choose m+1} \left( \frac {1}{t+\frac 12}\right)^{m+j+2} $$ and $$ L_{j,n} ...
2
votes
2answers
486 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 ...
3
votes
2answers
193 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 ...
1
vote
2answers
637 views

An identity involving a sum of binomial coefficients

I am moving through a classic paper (On Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my ...
5
votes
2answers
492 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 ...
0
votes
0answers
585 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
1
vote
2answers
352 views

Multinomial Coefficient Estimates

Hello, Let $B$ and $n$ be positive integers. Let $p_i \ge 0 $ be such that $\sum_{i=0}^{2B} p_i= 1$. I am interested in asymptotics (in terms of $B$, $n$, and $p_i$) for the coefficients of $ ...
0
votes
1answer
284 views

Sum involving integer compositions and binomial coefficients

I came across an identity involving binomial coefficients. I'm not sure if I'm looking at the identity the wrong way but I am not aware if this identity is known and if there is an (easy) proof for ...
4
votes
0answers
257 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}} = ...
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.
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} ...
3
votes
1answer
323 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
963 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 ...
29
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 ...
7
votes
0answers
312 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
471 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
465 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
325 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
631 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
1k views

non negative integer solutions : Diophantine Equations [closed]

I want to know the exact number of non-negative integer solutions of $a_1 + 2a_2 + \ldots + k \cdot a_k = n$. I know that it is the co-efficient of $x^n$ in $(1 - x^{a_1})^{-1} \cdot (1 - ...
0
votes
1answer
913 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
815 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
176 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
496 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
725 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
569 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
664 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
241 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
679 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
912 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 ...
9
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 ...
7
votes
0answers
715 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
541 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
788 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
734 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
675 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$, ...
18
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 ...