Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
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.


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