54 votes

A conjectural trigonometric identity

Let $T_n$ be the $n$-th Chebyshev polynomial, so that $$T_n(x)-1=\prod_{j=1}^n(x-\cos 2\pi j/n).$$ Taking a logarithmic derivative we have $$\sum_{j=0}^{n-1}\frac{1}{x-\cos 2\pi j/n}=\frac{T_n'(x)}{...
  • 25.2k
36 votes
Accepted

Sum over permutations is 1

Yes. Write the sum as $$ \sum_{\pi \in S_n} n! \int_0^{\infty} e^{-\pi(1) x_1} \int_{0}^{\infty} e^{-(\pi(1)+\pi(2)) x_2} \ldots \int_0^{\infty} e^{-(\pi(1) + \ldots +\pi(n))x_n} dx_n \ldots dx_1. ...
  • 42.7k
30 votes

A conjectural trigonometric identity

Denote $\omega=e^{2\pi i/n}$, then $\Omega=\{\omega^k:k=0,\ldots,n-1\}$ is the set of roots of the polynomial $f(t):=t^n-1$, $-\Omega=\{-\omega^k:k=0,\ldots,n-1\}$ the set of roots of $g(t):=t^n+1$. ...
29 votes

On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$

It is clear that $F_n(1)=0$. On the other hand, the derivative can be expressed in terms of $F_{n-2}$. Thus $$ \begin{aligned} F_n'(X) &=\sum_{k=0}^n\binom{n}{k}(-1)^k(k(n-k))X^{k(n-k)-1} \\ &=...
28 votes

Sum over permutations is 1

Here is a probabilistic, or, if you wish, combinatorial proof. Assume that we have $n$ baskets containing $z_1,\dots,z_n$ balls respectively (well, let them be positive integers). Choose a random ball ...
25 votes

Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$

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 $...
24 votes
Accepted

Has the $E_8$-based generating function for squares numbers been proven?

This identity was actually proven 24 years ago in S.O. Warnaar and P.A. Pearce, "Exceptional structure of the dilute A 3 model: E8 and E7 Rogers-Ramanujan identities" J.Phys. A27 (1994) L891-L898 ...
23 votes
Accepted

A special binomial identity in need of a proof

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

A cancellation property for permutations?

Let $n$ be some integer greater than 2. Since the number of even and odd permutations in $S_n$ is the same we have $\sum_{\sigma\in S_{n}}(-1)^{\ell(\sigma)}=0$ therefore the contribution of $\sum_{\...
22 votes

Sum over permutations is 1

Purely algebraic proof. We induct on $n$. Fix $\pi_n$. This part of the sum equals $z_{\pi_n}/(z_1+\dots+z_n)$ by induction proposition. Now sum up by all values of $\pi_n$.
22 votes
Accepted

A rather curious identity on sums over triple binomial terms

Just playing around with it: The RHS multiplied by $n$ is the same as $$2 \sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n}{k} \binom{n+1}{k+2}.$$ Subtracting this from $n$ times the LHS gives $$\sum_{k=0}^{n-...
20 votes
Accepted

A "quantum" identity: in search of a proof -Part II

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 ...
20 votes
Accepted

Identity with binomial coefficients and k^k

Let's denote $T(x)=\sum_{n\geq 1}\frac{n^{n-1}x^n}{n!}$ the exponential generating function of labeled rooted trees, and $U(x)=\sum_{n\geq 1}\frac{n^{n-2}x^n}{n!}$ the corresponding function for ...
19 votes
Accepted

An interesting identity: in search of a proof -Part I

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.
19 votes
Accepted

Catalan determinants in search of a proof: Part II

Here is a combinatorial proof. As my running example, I'll take $a=2$ and $n=3$, so I want to show $$\det \begin{bmatrix} 1 & 3 & 1 \\ 1 & 6 & 5 \\ 1 & 10 & 15 \\ \end{bmatrix}...
17 votes

Reference for exponential Vandermonde determinant identity

Write $\beta = \lambda_n$, the top row of your GT patterns. It's a theorem of [Baryshnikov] that if we choose a uniformly random point in the polytope GT${}_\lambda$, it's equivalent to choosing a ...
17 votes

Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$

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$ ...
16 votes
Accepted

In search of a combinatorial reasoning for a vanishing sum

For fixed $s,j>0$, $\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_j}$ enumerates the compositions of $j$ into $s$ positive parts by ordering the corresponding partitions. That is, we have $$\sum_{\...
16 votes

Products and sum of cubes in Fibonacci

This is just the following identity: $$a^3+b^3+c^3-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ca).$$ Since $$F_n+(-F_{n-1})+(-F_{n-2})=0,$$ your formula follows.
15 votes
Accepted

Products and sum of cubes in Fibonacci

$F_n$ is the number of compositions (ordered partitions) of $n-1$ into parts equal to 1 or 2. The number of triples $(a,b,c)$ of such compositions is $F_n^3$. The number such that $a,b,c$ all begin ...
14 votes
Accepted

Reference for exponential Vandermonde determinant identity

This looks like a special case of a formula by Samson Shatashvili related to the HCIZ integral as mentioned in Ryan's answer. Compare, in particular the two ways of computing $\langle 1\rangle$ given ...
14 votes

On the polynomial $\sum_{k=0}^n\binom{n}{k}(-1)^kX^{k(n-k)}$

$\def\gz{\frac{z^n}{(1+X)^{\binom n2}n!}} \def\tgz{{z^n}/{(1+X)^{\binom n2}n!}}$ Here's a combinatorial proof of the divisibility property for $F_n(X)$. It's enough to show that $$F_n(1+X) = \sum_{k=0}...
  • 14.5k
13 votes

An interesting identity: in search of a proof -Part I

Oh no, I was too slow... sorry for the double reference. This is Jensen's identity. It first appeared (in a slightly modified form) in: Jensen, Sur une identité d'Abel et sur d'autres formules ...
13 votes
Accepted

Sum of multinomals = sum of binomials: why?

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-...
  • 5,350
13 votes

Identity with binomial coefficients and k^k

Here are two proofs of your identity, which I have hinted at in my comments. The identity Let me first restate your identity with the letter $k$ renamed as $n$: Theorem 1. Let $n\geq2$ be an ...
13 votes
Accepted

A surprising identity: $\det[\cos\pi\frac{jk}n]_{1\le j,k\le n}=(-1)^{\lfloor\frac{n+1}2\rfloor}(n/2)^{(n-1)/2}$

First of all, we use the formula $$ D:=\det [x_j^k+x_j^{-k}]_{j,k=0,\dots,m-1}=\prod_{l<j}(x_j+x_j^{-1}-x_l-x_l^{-1})=\prod_{l<j} (x_j-x_l)(1-x_j^{-1}x_l^{-1}). $$ This follows from the ...
12 votes

Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$

Let us denote $$S=\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2.$$ First, let $s=i+j$ so that $$S = \sum_{s\geq 0}\sum_{i=0}^s \binom{s}{i}^2 \binom{a+b-s}{a-i}^2.$$ Consider the ...
11 votes

A relation between a binomial sum and a trigonometric integral

As I hinted in my comment, the $(-1)^k \binom{n}{k}...$ should set off alarm bells. There is for example a basic reciprocity law, that for functions $f, g: \mathbb{N} \to \mathbb{R}$, we have $$g(n) ...
  • 51.1k
11 votes
Accepted

A relation between a binomial sum and a trigonometric integral

You suspected right. It's easy. Convert $\sin^{2n+1}x=(1-\cos^2x)^n\sin x$ and integrate by substitution and apply binomial expansion $$\int_0^{\pi}\sin^{2n+1}x\,dx=2\int_0^1(1-u^2)^ndu=2\sum_{k=0}^n(-...
11 votes

A "quantum" identity: in search of a proof -Part II

If we substitute $y:=v+n$ in the identity, the LHS becomes a convolution of two similar sequences, $$\sum_{k=0}^nq^{(v+1)k}\binom{x+k}{k}_q \binom{v+(n-k)}{n-k}_q =\sum_{k=0}^n q^{n-k}\binom{x+v+n-k}{...
  • 52.5k

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