The binomial-coefficients tag has no wiki summary.
3
votes
3answers
297 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 ...
0
votes
1answer
50 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 ...
1
vote
0answers
125 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
194 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
202 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
3answers
505 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
93 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
159 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 ...
0
votes
1answer
174 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 ...
8
votes
2answers
797 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 ...
2
votes
3answers
540 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
64 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
145 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
313 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
65 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
429 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
63 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
208 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
156 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
92 views
1
vote
0answers
274 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 ...
1
vote
1answer
278 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,
...
17
votes
1answer
730 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
382 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 ...
0
votes
0answers
136 views
Sample size for Wilson's algorithm
Consider a story ranking website in which the ranking is crowd sourced from the number of up votes and down votes received by a story.
The score is computed as the lower bound Wilson's algorithm.
...
1
vote
0answers
66 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
383 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
2answers
125 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
497 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
393 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
358 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
217 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
243 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
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}} = ...
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
953 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
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} ...
1
vote
1answer
258 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
758 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
290 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
440 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
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 ...
6
votes
0answers
441 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
283 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
566 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
782 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
704 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
723 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 ...
