# Tag Info

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{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}$$ 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