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