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$. ...

- 92k

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} \\
&=...

- 43.3k

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 ...

- 92k

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 $...

- 92k

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
...

- 83k

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_{\...

- 83k

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$.

- 92k

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-...

- 7,262

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 ...

- 83k

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 ...

- 83k

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.

- 11k

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}...

- 143k

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 ...

- 6,401

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$ ...

- 2,726

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_{\...

- 27.6k

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 ...

- 46.1k

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 ...

- 20.1k

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 ...

- 1,374

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 ...

- 31.5k

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 ...

- 92k

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 ...

- 27.6k

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(-...

- 39.3k

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

#### Related Tags

combinatorial-identities × 141co.combinatorics × 86

nt.number-theory × 34

binomial-coefficients × 31

reference-request × 20

sequences-and-series × 16

determinants × 11

generating-functions × 11

permutations × 9

enumerative-combinatorics × 9

ca.classical-analysis-and-odes × 6

polynomials × 6

hypergeometric-functions × 6

elementary-proofs × 6

permanent × 6

linear-algebra × 5

prime-numbers × 5

q-analogs × 5

soft-question × 4

special-functions × 4

roots-of-unity × 4

stirling-numbers × 4

bernoulli-numbers × 4

ag.algebraic-geometry × 3

rt.representation-theory × 3