The tag has no wiki summary.

learn more… | top users | synonyms

8
votes
1answer
410 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}}}\,?$$
0
votes
1answer
68 views

Bounded convolutions with binomial coefficients

I need to figure out a nice family of decaying functions such that $\sum_{d=2}^k {k \choose d} f_k(d) \leq 1/k$ and $f_k(d)\geq f_k(d+1)$ How can I figure out what good candidates could be? Any ...
4
votes
0answers
194 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
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.
1
vote
0answers
150 views

An extrasensory perception strategy :-)

I asked this question at MSE some months ago but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
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 ...
3
votes
3answers
320 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 ...
2
votes
2answers
398 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 ...
1
vote
0answers
127 views

Asymptotic behaviour of sequence

I am interested in the sequence $$a(n)=\sum_{k=0}^n {p(n-k)-1 \choose k}$$ where $p(n)=(r-1)n^2+(2r-1)n+r$ for some $r \in \mathbb{N}$ or more generally any polynomial equation. When $r=1$ this ...
0
votes
1answer
219 views

Asymptotic growth for $\sum_{i=1}^{n-1}(n-i)\binom{k}{i}$ [closed]

For positive integers $n,k$, define $$f(n,k):=\sum_{i=1}^{n-1}(n-i)\binom{k}{i}.$$ What are upper and lower bounds of $f(n,k)$ by simpler terms? (e.g. finding bounds which are not a summation like ...
3
votes
1answer
210 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 ...
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 ...
6
votes
3answers
511 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 ...
2
votes
0answers
131 views

Sum of binomial coefficients weighted by a lower incomplete regularized gamma function

The following summation turned up in the course of my research: $$S_n=\sum_{k=0}^n {n \choose k}\lambda^k P(k,t)$$ where $P(k,t)=\frac{1}{\Gamma(k)}\int_{0}^t e^{-x}x^{k-1}dx$ is the lower ...
1
vote
1answer
166 views

Asymptotic behaviour of Binomial Sum

I am interested in the behaviour of: $\gamma_k=\sum_{i=0}^{k} {n \choose i}$ as n becomes large and where $k$ could potentially be a function of $n$ rather than a constant. One line of attack I can ...
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 ...
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 ...
0
votes
1answer
177 views

About the number of the elements of a set related with binomial coefficients

For $N\in\mathbb N$, let $$P_l(N)=\# \{(n,m)|0\le n\le N, 0\le m\le n,\binom{n}{m}\not\equiv 0 \mod l\}.$$ Suppose that $\binom{n}{0}=1$ for $n\ge 0$ and that $\# S$ represents the number of the ...
2
votes
2answers
541 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 ...
8
votes
2answers
811 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 ...
5
votes
2answers
400 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 ...
2
votes
3answers
551 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 ...
0
votes
0answers
68 views

Congruences for generalized Franel numbers

Let us define generalized Franel numbers $f^{(m)}_n$ through recurrence relations: $f^{(1)}_n=1$ for all $n$, and $$f^{(m)}_n=\sum\limits_{k=0}^n\binom{n}{k}^3f^{(m-1)}_k.$$ In fact ...
2
votes
1answer
146 views

Congruence for the Apery Numbers

Is it true that $$A_n\equiv (-1)^n\;\;(\mathrm{mod}\;3)\;\;?$$ Here $A_n$ is the Apery number: $$A_n=\sum\limits_{k=0}^n\binom{n}{k}^2\binom{n+k}{k}^2.$$ What is known about congruence properties ...
4
votes
1answer
317 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
0answers
209 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 ...
0
votes
0answers
79 views

Simplifying a finite difference sum that represents a model posterior to avoid numerical issues.

Problem Is it possible to simplify/rewrite the following expression, preferably without explicit sums, such that it can be computed without numerical issues when the $n_*$ are in the range of ...
6
votes
2answers
442 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 ...
4
votes
0answers
66 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
216 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
164 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
93 views

Resources on Wolstenholme's theorem

In Wikipedia entry on Wolstenholme's theorem, it says ...
1
vote
1answer
306 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, ...
1
vote
0answers
287 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 ...
17
votes
1answer
763 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
390 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
70 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
127 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
516 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 ...
0
votes
0answers
372 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
227 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
251 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 ...
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}$ ...
4
votes
0answers
232 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}} = ...
2
votes
3answers
990 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
782 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 ...
1
vote
1answer
261 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 ...
0
votes
0answers
171 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} ...
36
votes
2answers
2k 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 ...
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 ...