The binomial-coefficients tag has no wiki summary.
5
votes
0answers
65 views
An inequality concerning non-negative integer matrices with constant row and column sums
[I posted this question on math.stackexchange a few weeks back, but no luck there so far: ...
7
votes
1answer
336 views
Quest for a human proof of a $q-$binomial identity
Let $$f(n,k) = \sum\limits_{j = - k}^k {{{( - 1)}^{k - j}}}
\binom{n-j}{k-j}\binom{n+j}{k+j}.$$
Then $f(n,k)=\binom{n}{k}$
because it satisfies $f(n,k)=f(n-1,k)+f(n-1,k-1)$ and the obvious ...
9
votes
2answers
811 views
What is $\sum_{i=0}^{n}\binom{n}{i}^3$?
We know that $$\sum_{i=0}^{n}\binom{n}{i}=2^n$$
and that
$$\sum_{i=0}^{n}\binom{n}{i}^2= \binom{2n}{n}$$
what about
$$\sum_{i=0}^{n}\binom{n}{i}^3$$ ?
2
votes
1answer
261 views
$n^3 | \sum_{i=1}^{n-1}\binom{n}{i}^2$ => $n | \sum_{i=1}^{n-1}\binom{n}{i}$?
For $n\in \mathbf{N}$ is $$n^3 \text{ divides } \sum_{i=1}^{n-1}\binom{n}{i}^2=\binom{n}{1}^2+\cdots +\binom{n}{n-1}^2$$ impling $$n \text{ divides } ...
2
votes
1answer
125 views
Are binomial coefficients $F_1$ analogs of $q$-binomial coefficients?
This is a mostly philosophical question. Is it fair to think of usual binomial coefficients and their identities as an $F_1$ case of $q$-binomial coefficients and identities? Here $F_1$ is the field ...
5
votes
6answers
579 views
Binomial coefficient identity
It seems to be nontrivial (to me) to show that the following identity holds:
$$ \binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} \frac {n(-1)^k}{n+k} = 1. $$
This quantity is related to the volume of the ...
1
vote
0answers
45 views
closed form for a series with binomials and primes
does the series $\sum_{n=0}^\infty p^n \binom{x}{p^n}$ have a closed form ? ($p$ prime)
this is a special case of $\sum_{n=0}^\infty p^n \left(\sum_{k=p^n}^{p^{n+1}-1}a_k\binom{x}{k}\right)$ with the ...
16
votes
1answer
1k views
How to prove that the following double sum is always an integer？
I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple.
But I can not prove it. Proofs, hints, or references are all welcome.
Thanks!
...
3
votes
1answer
320 views
Simplest form for sum of Binomial Expressions
How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...
0
votes
0answers
44 views
bounds on a series with binomial coefficients
I have the following series
$\sum\limits_{l=1}^n {n\choose l} \alpha^{\beta^l}$
where $\alpha > 0$and $0 \leq \beta \leq 1$.
Can anybody guide me how I can evaluate it or find some tight upper ...
2
votes
1answer
133 views
Upper bound of sum of binomial coefficients
I am looking for an upper bound - up to constant factor - for:
$\sum_{k=t}^{t+l} {n \choose k} \cdot 2^{-n}$ where:
The values of $t$ are between: $\frac{n}2+\sqrt{n} \leq t \leq \frac{9n}{10}$. ...
4
votes
0answers
145 views
How find this binomial-coefficients sum $\sum_{k_{1}+k_{2}+\cdots+k_{d}=n}\binom{n}{k_{1},k_{2},\cdots,k_{d}}^2$ [duplicate]
Assmue that $d$ is give postive integer numbers,and
$$(x_{1}+x_{2}+\cdots+x_{d})^n=\sum_{k_{1}+\cdots+k_{d}=n} \binom{n}{k_{1},k_{2},\cdots,k_{d}}x^{k_{1}}_{1}x^{k_{2}}_{2}\cdots ...
16
votes
0answers
443 views
Does $\binom{2n}{n} \equiv 2 \pmod p$ ever hold?
Well, the title does not tell the whole story; the complete question is:
Are there any primes of the form $p=2n(n-1)+1$, with integer $n\ge 1$, such that
$$ \binom{2n}{n} \equiv 2\pmod p ? $$
...
1
vote
2answers
181 views
The zeros of alternating sign, binomial coefficient polynomials
I have a question regarding the zeros of the following polynomial, based on partial rows of pascal's triangle,
$$f(x)=\sum_{k=a}^n\binom{n}{k}(-1)^{k}x^k,$$
where $a,n\in \mathbb{Z}^+,n>a.$
...
0
votes
1answer
247 views
Maximize combinatorial sum for boolean function
I am trying to maximize the function
$$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$
for a function ...
1
vote
0answers
123 views
Solving a recurrence (with the form of a convolution) involving binomial coefficients
While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$
\begin{array}{cccccccccc}
1 & = & ...
5
votes
4answers
390 views
Maximum value of the binomial coefficient as a polynomial
What is the maximum (absolute) value of the binomial coefficient
$\begin{pmatrix}x \\ k\end{pmatrix} = \frac{1}{k!}x(x-1)(x-2)\dotsb(x-k+1)$
for real $x$ in the interval $0 \leq x \leq k-1$?
23
votes
1answer
552 views
integers which are sums of binomial coefficients: $\sum_i {n \choose k_i}$
Let $n$ be an integer. For $S$ a subset of $\{0,\dots,n\}$, define
$$m(S) = \sum_{k \in S} {n \choose k}.$$
Let $M_n$ be the set of integers of the form $m(S)$ for all sets $S \subset \{0,\dots,n\}$. ...
2
votes
1answer
172 views
Combinatorial sum (Author and generalization?)
In a book I have met one interesting equation (without reference):
$$\frac{m!}{n!}\sum_{i=0}^n(-1)^i{n\choose{i}}{x+m+n-i\choose{m}}=\begin{cases}
x+n+1,\, if \,m=n+1
\\
1,\, if \,m=n
\\
...
0
votes
0answers
94 views
Estimating when does a certain binomial sum exceed an upper bound
Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers
$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$
For example $f_{n,0} = ...
1
vote
1answer
147 views
Polynomial convex coefficients
Assume we have an arbitrary high order polynomial $$f(L)=1-L\theta_1-L^2\theta_2-L^3\theta_3-...-L^N\theta_N$$ and we know all roots of this polynomial site outside the unit circle. It is obvious that ...
8
votes
1answer
461 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}}}\,?$$
4
votes
0answers
333 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 ...
1
vote
0answers
173 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 ...
3
votes
3answers
394 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 ...
1
vote
1answer
184 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 ...
2
votes
2answers
332 views
Asymptotic behaviour of sequence
I am interested in the sequence
$$a(n)=\sum_{k=0}^n {p(n-k) \choose k}$$
where $p(n)$ is a polynomial equation.
When $p(n)=n$ this reduces to the Fibonacci sequence, but what about when $p(n)$ is ...
0
votes
1answer
342 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
253 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
573 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
201 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
207 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
183 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 ...
7
votes
2answers
954 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
626 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
1answer
103 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
160 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
331 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
244 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
...
6
votes
2answers
470 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
74 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
263 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
215 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
116 views
1
vote
0answers
359 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
536 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
864 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
414 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
78 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
463 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 ...
