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

learn more… | top users | synonyms

19
votes
1answer
1k 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}$, ...
1
vote
1answer
195 views

Simplify a equation

I have a problem simplifying the summation here: $$ \sum_{x=0}^{n}\sum_{y=0}^{x} {n\choose{x}} {x\choose{y}} y!(x-y)! $$ The last three terms can be simplified to x!, so the current summation ...
5
votes
1answer
214 views

Estimate of incomplete binomial integral

Let $0\le k \le n$. Prove that $$ n\binom{n}{k}\int_{0}^{\frac{k}{n+1}}t^k(1-t)^{n-k}\,dt \le 1/2. $$ As far as I know 1) it is proved for $\frac{k}{n+1}\le 1/2$ and 2) not proved for $1/2 <\frac{...
16
votes
1answer
756 views

Are there good bounds on binomial coefficients?

Motivated by the central limit theorem, one expects that $$\binom{n}{k} \approx \frac{2^n}{\sqrt{\pi n/2}} \exp\left(-\frac{(k-n/2)^2}{n/2}\right).$$ Computations suggest that the ratio of the two ...
10
votes
2answers
620 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 ...
8
votes
0answers
539 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$. \begin{align} P_{0,0}&=1\\ \text{for $n\geq 1$}...
4
votes
3answers
394 views

On a theorem of Hensel about congruence of binomial coefficient

In the paper Binomial coefficients modulo prime powers, Andrew Granville stated the following theorem: Let $n, m$ and $r=n-m$ be three given positive integer and $p^k$ is the exact power of $p$ ...
1
vote
0answers
84 views

Sum of products of binomial coefficients

I have been trying to check that two things are equal for a while now, Mathematica appears to say that they are but I can't for the life of me figure out how to show it (without just saying 'computer ...
1
vote
1answer
218 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 ...
23
votes
3answers
3k views

Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$

I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$. Some clues that might work (kindly provided by ...
5
votes
2answers
384 views

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

Let $\binom x y$ be the binomial coefficient. I am trying to get a better understanding of the sum $$ f(N,\lambda)=\sum_{n=0}^{N-1}\binom{N-1}n\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda} $$ as a ...
2
votes
0answers
85 views

A combinatorial sum involving ratios of binomials [closed]

Can anyone suggest how to prove the following (for $k \le n$): $$\sum \limits_{s=0}^N \frac{\binom{n}{k} \binom{N-n}{s-k} }{\binom{N}{s}} = \frac{N+1}{n+1}$$ I am assuming it to be true, and ...
7
votes
6answers
883 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 ...
13
votes
1answer
386 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 ...
6
votes
3answers
520 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 $(1-4x)^...
2
votes
1answer
151 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
108 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 ...
3
votes
1answer
154 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 \left(\binom{p^{r+1}}{1},\binom{p^{r+1}}{p^...
1
vote
1answer
56 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 theorem:...
3
votes
1answer
140 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
54 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 $(1-z)^{-a}(1-z)^{-b}=...
2
votes
1answer
213 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 - ...
6
votes
1answer
598 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
1answer
155 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
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 ...
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 ...
4
votes
3answers
162 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 $(n!)^...
3
votes
1answer
163 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
148 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 ...
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 - x^{a_2})^{-...
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
248 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 ...
3
votes
2answers
155 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
385 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 ...
0
votes
1answer
290 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 $f:\...
3
votes
3answers
422 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
456 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
315 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
239 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 ...
0
votes
1answer
135 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 $$f^{(m)}_n=\sum\...
5
votes
0answers
142 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: http://math.stackexchange.com/questions/1095659/an-inequality-concerning-non-negative-integer-matrices-with-...
7
votes
1answer
378 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
866 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
288 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 } \sum_{i=1}^{n-1}\binom{n}{i}=\binom{n}{1}+\...
15
votes
2answers
2k views

Binomial supercongruences: is there any reason for them?

One of the recent questions, in fact the answer to it, reminded me about the binomial sequence $$ a_n=\sum_{k=0}^n{\binom{n}{k}}^2{\binom{n+k}{k}}^2, \qquad n=0,1,2,\dots, $$ of the Apéry ...
2
votes
1answer
167 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 ...
1
vote
0answers
65 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! $$\sum_{m=s}^{2s}\sum_{k=0}^{...
2
votes
1answer
245 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
151 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 x^{k_{d}}_{d}$$ ...