Skip to main content
MathOverflow

Return to Answer

added 6 characters in body
Source Link
Fedor Petrov
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

  1. If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

  2. Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\,\text{if}\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

  3. If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_1^n+\dots+x_{n+1}^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^i\binom{n}{i}$$c_i=(-1)^{i-1}\binom{n}{i-1}$ satisfy thosethese relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

  1. If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

  2. Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\,\text{if}\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

  3. If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_1^n+\dots+x_{n+1}^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^i\binom{n}{i}$ satisfy those relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

  1. If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

  2. Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\,\text{if}\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

  3. If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_1^n+\dots+x_{n+1}^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^{i-1}\binom{n}{i-1}$ satisfy these relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.

added 4 characters in body
Source Link
Fedor Petrov
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

  1. If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

  2. Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}(-1)^{k-1}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$$$\Phi[f]=\begin{cases}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\,\text{if}\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

  3. If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_0^n+\dots+x_n^n)=0$$c_0+\dots+c_n=\Phi(x_1^n+\dots+x_{n+1}^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^i\binom{n}{i}$ satisfy those relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

  1. If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

  2. Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}(-1)^{k-1}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

  3. If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_0^n+\dots+x_n^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^i\binom{n}{i}$ satisfy those relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

  1. If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

  2. Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\,\text{if}\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

  3. If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_1^n+\dots+x_{n+1}^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^i\binom{n}{i}$ satisfy those relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.

Source Link
Fedor Petrov
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

  1. If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

  2. Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}(-1)^{k-1}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

  3. If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_0^n+\dots+x_n^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^i\binom{n}{i}$ satisfy those relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.