The tag has no usage guidance, but it has a tag wiki.

learn more… | top users | synonyms

13
votes
1answer
357 views

A combinatorial identity involving generalized harmonic numbers

The $n$-th harmonic number is defined as $$ H_n=\sum_{k=1}^{n}\frac{1}{k}, $$ and the generalized harmonic numbers are defined by $$ H_{n}^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}. $$ Recently, I have found ...
2
votes
1answer
137 views

Alternating sign binomial identity [closed]

I recently noticed that for a triple of integers $k \geq 2$, $k \geq m \geq t \geq 1$, the following identity seems to hold $\sum_{j=0}^{m-t} (-1)^{m-t-j}{k \choose j}{m-1-j \choose t-1}={k-t \choose ...
0
votes
0answers
81 views

Partial sum of binomial coefficients

For some integer $z \ge 2$ and large integer $n$ and $ t=\lceil \log n\rceil $, what is an approximate value for the following partial binomial sum? $$ \sum_{i=0}^{n-t} \binom{n}{i}z^i .$$ Another ...
4
votes
2answers
310 views

Can you simplify (or approximate) $\sum_{n=0}^{N-1}\begin{pmatrix}N-1\\n\end{pmatrix}\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?

Let $\begin{pmatrix}x\\y\end{pmatrix}$ be the binomial coefficient. I am trying to get a better understanding of the sum \begin{equation} ...
1
vote
1answer
50 views

Summation of multinominal coefficients with extra bounds on summation indices

My question is related to the sum \begin{equation} S(n,N) = \sum_{k_1+k_2+...+k_N=n}\frac{n!}{(k_1!)\cdot(k_2!)\cdot...\cdot(k_N!)} = N^n, \end{equation} which is comes from the multinomial ...
3
votes
1answer
134 views

Asymptotic for binomial sums

Let $S(n, t) = \sum_{k = 0}^n {n \choose k} ^t$. The task is to find asymptotic behavior of $S(n,5)$, $n \to \infty$. Asymptotic for $S(n,0)$ and $S(n,1)$ is very simple. For $S(n,2)$ we can use ...
3
votes
0answers
47 views

How to prove that $\sum_{i=0}^n\frac{(a;q)_i}{(q;q)_i}\frac{(b;q)_{n-i}}{(q;q)_{n-i}}a^{n-i}=\frac{(ab;q)_n}{(q;q)_n}$?

By Cauchy identity, $${}_1\phi_0(a;—;q,z)=\sum_{n\geq0}\frac{(a;q)_n}{(q;q)_n}z^n=\frac{(az;q)_{\infty}}{(z;q)_\infty},\quad|z|<1,|q|<1,$$ we can obtain the $q-$analogue of ...
2
votes
1answer
190 views

Asymptotic of a sum involving binomial coefficients

Good evening, I'm trying to find an asymptotic of this sum: $$\sum_{j=0}^n (-1)^j {n \choose j} (n - j)^n = n^n - {n \choose 1} (n - 1)^n + {n \choose 2} (n - 2)^n + ... + (-1)^n {n \choose n} (n - ...
1
vote
1answer
150 views

limit and combinatorics

Given $x \in (0,\frac{1}{2})$ and $y \in (0,\frac{1}{2}]$, what is the value of the following limit: $\lim_{n\rightarrow \infty}\sum_{k=0}^{n}{n \choose k}|x^{n-k}(1-x)^{k}-y^{n-k}(1-y)^{k}|?$ When ...
3
votes
1answer
151 views

Effective Realization of GCD of middle binomials?

So, it is well-known that $$ \gcd \left(\binom{m}{k}\mid 1\leq k\lt m \right) = e^{\Lambda(m)}$$ which can incidentally be sparsified for prime $p$ $$ \gcd ...
4
votes
3answers
160 views

Asymptotic expression for $j$ which satisfies $\binom{n}{j}/j! \sim k$ as $n\to\infty$

Suppose $k>0$ is some fixed constant, and $n$ is a positive integer tending to infinity. Find $j\equiv j(n,k)$ such that $$ \frac{\binom{n}{j}}{j!} \sim k. $$ The asymptotic expression for ...
3
votes
1answer
131 views

Closed Form Expression for Nested Series Summation?

Just wandering if there are any criteria that can decide whether a finite series summation has closed form or not. for example, In the following nested summation, $n$ is some even integer that will be ...
2
votes
0answers
140 views

binomial coefficients and irrationals

The following, probably either currently impossible to deal with, or having a negative solution, arose from an ergodic theory question, presumably itself currently intractible. I am not a number ...
15
votes
1answer
1k views

Prove that expression is integer

Numerical experiments suggest that $\binom{2m}{m + k}\cdot\frac{3m - 1 - 2k^2}{2m - 1}$ is integer for all $-m \le k\le +m$. It means that expression evaluation could be implemented very efficiently, ...
2
votes
2answers
237 views

binomial/factorial identity mod p

In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result. Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive ...
42
votes
1answer
3k views

How to prove this polynomial always has integer values at all integers?

Let $m$ be any positive integer. $$ P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}{x+j\choose j}{x-1\choose j}{j\choose i}{m\choose i}{i\choose m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}. $$ Question: $P_m(x)$ always ...
3
votes
2answers
149 views

Closed form for binomial coeff sum

As part of a proof in finite group theory, I'm looking for a closed form for the expression $$\sum_{i=j+1}^{n} \binom{\binom{i}{j}}{2}$$ Any help - especially with reference or proof - would be ...
9
votes
1answer
362 views

Equation with $q$-binomial coefficients

Let $d\ge2$, and let $q$ be a power of a prime. As usual, define $N(d,q)=\sum_{k=0}^d{d\choose k}_q$. I wonder if there are $d$ and $q$ as above such that $1+N(d,q)=q^{d+1}$. (If the answer is ...
3
votes
3answers
407 views

A question about summation formula involving binomial coefficient

In Table of Integrals, Series, and Products. Seventh Edition. I.S. Gradshteyn and I.M. Ryzhik, there is 0.154.3 $$ \sum_{k=0}^N (-1)^k {N \choose k} k^{n-1} =0, N \geq n \geq 1; 0^0 ≡ 1 $$ 0.154.4 ...
1
vote
2answers
203 views

Partial Sum of the Binomial Theorem [duplicate]

The binomial theorem states $\sum_{k=0}^nC_n^kr^k=(1+r)^n$. I am interested in the function \begin{equation} \sum_{k=0}^mC_n^kr^k, \quad m<n \end{equation} for fixed $n$ and $r$, and both $m$ and ...
5
votes
2answers
282 views

Combinatorial identity and Fuss-Catalan numbers

I would like to show that $$ \lim_{N\to\infty}\frac{1}{N^{np+1}}\frac1{p!}\sum_{j=0}^{p-1}(-1)^j\binom{p-1}{j} \left(\frac{\Gamma(N+p-j)}{\Gamma(N-j)}\right)^{n+1} =\frac1{np+1}\binom{(n+1)p}{p}, $$ ...
1
vote
1answer
229 views

Asymptotic of a certain double sum involving binomial coefficients

Consider sums of the form $S(n)=\sum^{n}_{m=0}\sum^{m}_{k=1}2^{2k+m+1}{n-m+k+1 \choose 2k+2}{m \choose k}$ I am interested in the asymptotics of $S(n)$ as $n\to \infty$. More precisely I would ...
5
votes
0answers
129 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
376 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
861 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
281 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
161 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 ...
7
votes
6answers
843 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
61 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 ...
17
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! ...
15
votes
1answer
893 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}$, ...
2
votes
1answer
207 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
149 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 ...
18
votes
0answers
559 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
272 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
287 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
149 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
599 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
597 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
183 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
107 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
170 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
494 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}}}\,?$$
6
votes
1answer
562 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
202 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
448 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 ...
3
votes
1answer
258 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
356 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
438 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
306 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 ...