46

In terms of hypergeometric series, the sum is $_3F_2(-n, 1+n, 1/2;1,3/2;1)$ and the identity is a special case of Saalschütz's theorem (also called the Pfaff-Saalschütz theorem), one of the standard hypergeometric series identities.
A more general identity, also a special case of Saalschütz's theorem, is
$$\sum_{k=0}^n (-1)^k\frac{a}{a+k}\binom{n+k+b}{n-k}...

44

Here's a proof of the positivity of
$$
c_n(\alpha) := \sum_{r=0}^n (-1)^r {n\choose r}^\alpha
$$
for all even $n$ and real $\alpha < 1$. It follows
(via M.Wildon's clever $F(x) F(-x)$ trick at mo.84958) that
$\sum_{n=0}^\infty \phantom. x^n / n!^{\alpha} > 0$ for all $x \in\bf R$.
[EDIT fedja has meanwhile provided a very nice direct proof of
the ...

39

It equals
$$
\binom{2m}{m+k}\frac{3m-1-2k^2}{2m-1}=-(m-1)\binom{2m}{m+k}+4m\binom{2m-2}{m+k-1}.
$$
I got it by expanding $3m-1-2k^2=2(m^2-k^2)-(2m^2-3m+1)=2(m-k)(m+k)-(2m-1)(m-1)$.

33

$$P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}\binom{x+j}{ j}\binom{x-1}{ j}\binom{j}{ i}\binom{m}{ i}\binom{i}{ m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}.$$
Our task is to show it takes integer values on integers.
Folowing Wadim Zudilin we put
$$B_k(x)=\binom{x+k}{2k}+\binom{-x+k}{2k}.$$
For $k\geq0$ the $B_k$ are even polynomials of degree $2k$ that take integer ...

30

The following proof of $c_n>0$ is based on Gjergji Zaimi's response to this related question. In particular the positive answer follows for that question, too. Moreover, the argument below should also show that $c_n>c_{n+2}$.
Let $n>0$ be even. By Chapter 6 of de Bruijn's "Asymptotic Methods in Analysis" (in particular by (6.4.6), (6.6.2), and the ...

28

Here is a short proof of the more general identity
$$ \sum_{k=0}^{2m} (-1)^k \binom{2m}{k} \binom{x}{k}\binom{x}{2m-k} = (-1)^m \binom{2m}{m} \binom{x+m}{2m}. $$
Considered as polynomials in $x$, both sides have degree $2m$. If $x = m$ then $\binom{x}{k}\binom{x}{2m-k}$ is non-zero only when $k=m$, and so both sides equal $(-1)^m \binom{2m}{m}$. If $x \in \...

27

This is the answer to the first question, I wrote a long answer to Question 2 as a separate answer.
Note that $A:=\sum_{k_i>0,k_1+\dots+k_n=K}\frac{K!}{n!k_1!\dots k_n!} \prod k_i^{k_i-1}$ is a number of forests on the ground set $\{1,2,\dots,K\}$ having exactly $n$ connected components and with a marked vertex in each component ($k_i$ correspond to the ...

26

Using the integral representation of Bernoulli numbers I obtain formally the integral representation of the double summation
$$
\sum_{k=1}^{\infty}\sum_{j=0}^{k}\binom{k}{j}\frac{B_{j+k+1}}{j+k+1}=2\cdot\int_0^\infty\frac{t}{e^{2 \pi t}-1}\frac{dt}{t^2+(1+t^2)^2}=0.069591059035995961110566767049...
$$
So the alternative form of the question is
$$
\int_0^\...

25

Denote $h(x,y)=\sum_{i,j\geqslant 0} \binom{i+j}i x^iy^j=\frac1{1-(x+y)}$, $f(x,y)=\sum_{i,j\geqslant 0} \binom{i+j}i^2 x^iy^j$. We want to prove that $2xyf^2(x^2,y^2)$ is an odd (both in $x$ and in $y$) part of the function $h(x,y)$. In other words, we want to prove that $$2xyf^2(x^2,y^2)=\frac14\left(h(x,y)+h(-x,-y)-h(x,-y)-h(-x,y)\right)=\frac{2xy}{1-2(x^...

23

The $k=j-1$ and $k=-j$ terms cancel, so all that's left is the $k=n$ term.

22

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have
$$
\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}
$$
where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling and then some other ...

19

Both sides are equal to $\binom{x+y+1}{n}_q$. This enumerates lattice paths in an $n\times (x+y-n+1)$ rectangle, according to the area statistic. We will assume that these paths start at $(0,0)$ and end at $(x+y-n+1,n)$, and they are only directed East or North. Here are two ways to enumerate it:
First count: For each path there will be a unique $k$, so it ...

17

[Revised and expanded to give the answer for all $k>1$ and incorporate
further terms of an asymptotic expansion as $n \rightarrow \infty$]
Fix $k>1$, and write $a_1=f(1,k)=1$ and
$$
a_n = f(n,k) =
\frac1{1-q^{-n}} \sum_{r=1}^{n-1} {n \choose r} (1/k)^{n-r} (1/q)^r a_r
\phantom{for}(n>1),
$$
where $q := k/(k-1)$, so $(1/k) + (1/q) = 1$. Set
$$
a_\...

17

This is known as Jensen's identity and dates back to 1902. See here an overview of this identity and related ones, and a proof: https://arxiv.org/abs/1005.2745, a paper by Victor Guo.

co.combinatorics sequences-and-series binomial-coefficients enumerative-combinatorics combinatorial-identities

16

After canceling $1$'s and clearing denominators, the identity can be rearranged to this one:
$$n^{n+1} = \sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k+1} + \sum_{k=1}^n \binom{n}{k} n^{n-k} k!$$
and now we proceed to give a bijective proof. The left side counts data of the form
Endofunction $f: S \to S$ on an $n$-element set $S$, plus a distinguished ...

16

Here is an attempt at an answer. We assume that the recurrence from my comment above holds [with a small correction] (a proof was obtained by Kevin using Zeilberger's algorithm, see the comment below):
$$ (7s+8)(s+4)(s+3)^2 a_{s+3} - 4(56s^2+127s+57)(s+3)(s+2) a_{s+2} $$
$$ - 16(7s^4-6s^3-121s^2-210s-90) a_{s+1} + 128(7s+15)(2s+3)(2s+1)(s-1) a_s = 0 $$
Write ...

16

I don't know if there is a relation for values of $\ell$ apart from $1$ and $2$ (that would be very interesting, and surprising to me), but here is a unified way to look at what's going on for exponents $1$ and $2$.
Consider the function on ${\Bbb R}$ defined by
$$
f(x) = (1+e^{2\pi i x})^n
$$
for $-1/2 \le x \le 1/2$ and $f(x) = 0$ if $|x| >1/2$. ...

16

When this identity was posted, it struck me as something that ought to have a combinatorial explanation. I have now found one, using a decomposition of NSEW lattice paths: paths in $\mathbb{Z}^2$ consisting of unit steps in the direction N, S, E or W. Many of the ideas here may be found in [GKS], though not the decomposition itself.
The expression $\frac12{...

15

We have
$$\sum_l\binom{a+l}lx^l=\frac1{(1-x)^{a+1}},$$
hence the generating function for the even terms of the sequence is
$$\sum_l\binom{a+2l}{2l}x^{2l}=\frac12\left(\frac1{(1-x)^{a+1}}+\frac1{(1+x)^{a+1}}\right).$$
Consequently,
\begin{multline*}\sum_l\binom{a+2l}{2l}\binom{b+2(n-l)}{2(n-l)}=\\\\
[x^{2n}]\frac14\left(\frac1{(1-x)^{a+1}}+\frac1{(1+x)^{a+1}}\...

14

No, there are no others.
In fact, define a function $q : \mathbb N\to\left\lbrace 1,-1\right\rbrace$ by $q\left(i\right) = \left(-1\right)^i p\left(i\right)$ for every $i\in\mathbb N$. Then, $\sum\limits_{i=0}^n p\left(i\right) \binom{n}{i} = 0$ becomes $\sum\limits_{i=0}^n \left(-1\right)^i q\left(i\right) \binom{n}{i} = 0$. Now, denote, for every $n,x\in\...

14

Yes, there are nontrivial solutions. The first I found, with $n=5$, has
$$
\lbrace x_i \rbrace = \lbrace 2, 5, 8, 13, 19 \rbrace,
\phantom{\infty}
\lbrace y_i \rbrace = \lbrace 3, 4, 6, 14, 20 \rbrace,
$$
with $\sum_i x_i = \sum_i y_i = 47$ and
$$
\prod_{i=1}^5 {2x_i \choose x_i} = \prod_{i=1}^5 {2y_i \choose y_i}
= 7153522697506948963200000
= 2^{10} 3^6 ...

14

Consider the contour integral of
$$
\frac{1}{z} \prod_{k=v}^{n} \frac{k^2}{k^2-z^2}
$$
over a circle of large radius centered at $0$. Since the integrand is
small as $|z|\to \infty$ the answer must go to zero as the radius goes to infinity.
But inside the circle there are poles at $z=0$ and $z= \pm k$ for $k$ from $v$ to $n$. Computing the residues ...

14

Denote the sum of the digits of $n$ in base $b$ by $S(n)$. Then the number of carries when adding $k_1+k_2$ is
$$\frac{1}{b-1}\big(S(k_1)+S(k_2)-S(k_1+k_2)\big).$$
This shows that the number of carries when successively adding $(((k_1+k_2)+k_3)+\cdots +k_r)$ is
$$\frac{1}{b-1}\left(\sum_{i=1}^r S(k_i)-S\left(\sum_{i=1}^r k_i\right)\right),$$
and this last ...

13

The first formula is a special case of one of the standard hypergeometric series summation formulas called Kummer's theorem. (See, e.g.,
http://mathworld.wolfram.com/KummersTheorem.html or
http://en.wikipedia.org/wiki/Hypergeometric_function#Kummer.27s_theorem.)
The first formula may be written as
$$\sum_{k=0}^n \binom{4n+1}{k} \binom{3n-k}{n-k} = 2^{2n} \...

13

The identity
$$
\begin{align}
\sum_{s=1}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s }{s+1}H_{s}^{(2)}=\frac{2(-1)^m}{m+1}\sum_{s=1}^m H_{s}^{(2)}. \tag{1}
\end{align}
$$
is equivalent to the following identity
$$
\sum_{s=1}^{m}{2s\choose s}\frac{H_s^{(2)}}{s+1}(x-x^2)^s=\frac{2\text{Li}_2(x)}{1-x}-\frac{\ln^2(1-x)}{x},\tag{2}
$$
where $\text{Li}_2$ is ...

13

Let's re-index the sum on the LHS of the problem (for the below convenience) so that
$$\frac1s\sum_{k=0}^{s-1}\binom{s+k-1}k(s-k)v^{s-k}(v-1)^k
=\frac{v}s\sum_{k=0}^{s-1}\binom{2s}k(s-k)(v-1)^k.$$
Or, just pull out the $v$ factor (leaving behind $\frac1s$, again for convenience):
$$\frac1s\sum_{k=0}^{s-1}\binom{s+k-1}k(s-k)v^{s-1-k}(v-1)^k
=\frac1s\sum_{k=0}^...

13

For convenience set $m=n-2k$. Then
\begin{equation}
\begin{split}
\binom{n-2k+j}{j,k-2j,n-3k+2j} &= \binom{m+j}{j,k-2j,m-k+2j} \\
&= \binom{m+j}{m} \binom{m}{k-2j} \\
&= [t^j](1-t)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m \\
&= [t^{2j}](1-t^2)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m
\end{split}
\end{equation}
where $[t^a]p$ is the coefficient ...

13

By Cauchy–Bunyakovsky–Schwarz inequality we have
$$
\left(\sum \prod_i \frac{\binom{a_i}{b_i}}{\binom{A-a_i}{B-b_i}}\right)\left(\sum\prod_i \binom{a_i}{b_i}\binom{A-a_i}{B-b_i}\right)\geqslant
\left(\sum \prod_i\binom{a_i}{b_i}\right)^2=\binom{A}{B}^2
.$$
Thus it suffices to prove that
$$
\sum\prod_i \binom{a_i}{b_i}\binom{A-a_i}{B-b_i}\leqslant \binom{A}...

12

Consider the generating series
$$\sum_{s=0}^{\infty}\left(\sum_{i+j=s}\binom{A-n+j}{j}\binom{n-j}{i}\right)x^{s}.$$ This equals $$\sum_{j=0}^{\infty}\binom{A-n+j}{j}x^{j}\sum_{i=0}^{\infty}\binom{n-j}{i}x^{i}=(1+x)^{n}\sum_{j=0}^{\infty}\binom{A-n+j}{j}\left(\frac{x}{1+x}\right)^{j},$$ where we use the binomial theorem for the last equality. As $\sum_{k=0}^{...

12

First, what the Stirling bound or Stanica's result give is already a $(1+O(n^{-1}))$ approximation of $\binom nk$, hence the only problem can be with the sum. I don't know how to do that with such precision, but it's easy to compute it up to a constant factor by approximating with a geometric series:
$$\sum_{i\le k}\binom ni=\begin{cases}\Theta(2^n)&k\...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

binomial-coefficients × 225co.combinatorics × 139

nt.number-theory × 43

asymptotics × 25

sequences-and-series × 23

combinatorial-identities × 20

reference-request × 14

q-analogs × 8

real-analysis × 7

inequalities × 7

limits-and-convergence × 7

generating-functions × 7

hypergeometric-functions × 7

ca.classical-analysis-and-odes × 6

polynomials × 6

special-functions × 6

additive-combinatorics × 6

prime-numbers × 5

enumerative-combinatorics × 5

pr.probability × 4

linear-algebra × 4

determinants × 4

congruences × 4

catalan-numbers × 4

matrices × 3