|
|
https://artofproblemsolving.com/community/c728438h2121954_summation_with_polynomial_roots
Identity of a conditional symmetric polynomial
Let $\displaystyle S_{n,m}=\sum_{r_1+r_2+\cdots+r_m=n} x_1^{r_1}x_2^{r_2}\cdots x_m^{r_m},~\sigma_{k,m} =\sum_{1\le j_1 < j_2 < \cdots < j_k \le m} x_{j_1} \dots x_{j_k}$
$\displaystyle \boxed{S_{j,m}=\sum_{k=1}^{m-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{m-1}\sigma_{m,m} S_{j-m,m}}$
$\displaystyle \text{or}~ \boxed{S_{j,m}=\sum_{k=1}^{j-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{j-1}\sigma_{j,m}}$
Proof
Distribute $n$ balls into $m$ boxes
Each box $k=1,2,\cdots,m$ has $r_k$ balls
Let $A_k$ be the event of box $k$ contains at least one ball
By Inclusion–exclusion principle
$\displaystyle \left|\bigcup_{i=1}^m A_i\right| = \sum_{i=1}^m |A_i| - \sum_{1 \le i < j \le m} |A_i\cap A_j| + \sum_{1 \le i < j < k \le m} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{m-1} \left|A_1\cap\cdots\cap A_m\right|$
satisfies for the number of any combinations of $\{r_k\}$, therefore
$\displaystyle \boxed{S_{j,m}=\sum_{k=1}^{m-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{m-1}\sigma_{m,m} S_{j-m,m}}$
$\displaystyle \text{or}~ \boxed{S_{j,m}=\sum_{k=1}^{j-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{j-1}\sigma_{j,m}}$
Example
For the combination $\{2,1,0\}$ as example
$|A_1\cup A_2\cup A_3|=1$
$|A_1|=|A_2|=1,~|A_3|=0$
$|A_1\cap A_2|=1,~|A_1\cap A_3|=|A_2\cap A_3|=0$
$|A_1\cap A_2\cap A_3|=0$
$1=2-1+0$
which is the same as the situation of the coefficient of $a^2 b$
$\displaystyle \sum_{r_1+r_2+r_3=3} a^{r_1}b^{r_2}c^{r_3}
=(a+b+c)\sum_{r_1+r_2+r_3=2} a^{r_1}b^{r_2}c^{r_3}
-(ab+ac+bc)\sum_{r_1+r_2+r_3=1} a^{r_1}b^{r_2}c^{r_3}
+abc$
Other examples
$a^n=a(a^{n-1})$
$a^3+a^2 b+ab^2+b^3=(a+b)(a^2+b^2+ab)-(ab)(a+b)$
$\displaystyle S_{j,K}=\sum_{k=1}^{M-1} (-1)^{k-1}
\sigma_{k,M} S_{j-k,K}+(-1)^{M-1}\sigma_{M,M}S_{j-M,K},~\forall K\le M\le m$
Proof
$\displaystyle S_{j,K}=\sum_{k=1}^{K-1} (-1)^{k-1} \sigma_{k,K} S_{j-k,K}+(-1)^{K-1}\sigma_{K,K}S_{j-K,K}$
Suppose $\displaystyle S_{j,K}=\sum_{k=1}^{M-1} (-1)^{k-1}
\sigma_{k,M} S_{j-k,K}+(-1)^{M-1}\sigma_{M,M}S_{j-M,K}$ is true for $M$
$\displaystyle S_{j-1,K}=\sum_{k=1}^{M-1} (-1)^{k-1}
\sigma_{k,M} S_{j-1-k,K}+(-1)^{M-1}\sigma_{M,M}S_{j-1-M,K}$
$\displaystyle 0=-S_{j-1,K}+\sum_{k=2}^M (-1)^{k-2} \sigma_{k-1,M} S_{j-k,K}+(-1)^{M-1}\sigma_{M,M}S_{j-1-M,K}$
$\displaystyle 0=x_{M+1}S_{j-1,K}+\sum_{k=2}^{M-1} (-1)^{k-1} x_{M+1}\sigma_{k-1,M} S_{j-k,K}$
$+(-1)^{M-1}x_{M+1}\sigma_{M-1,M}S_{j-M,K}
+(-1)^M x_{M+1}\sigma_{M,M}S_{j-1-M,K}$
$\displaystyle S_{j,K}=(x_{M+1}+\sigma_{1,M})S_{j-1,K}
+\sum_{k=2}^{M-1} (-1)^{k-1}
(x_{M+1}\sigma_{k-1,M}+\sigma_{k,M}) S_{j-k,K}$
$+(-1)^{M-1}(x_{M+1}\sigma_{M-1,M}+\sigma_{M,M})S_{j-M,K}
+(-1)^M x_{M+1}\sigma_{M,M}S_{j-1-M,K}$
$\displaystyle S_{j,K}=\sigma_{1,M+1}S_{j-1,K}+\sum_{k=2}^{M-1} (-1)^{k-1} \sigma_{k,M+1} S_{j-k,K}$
$+(-1)^{M-1}\sigma_{M,M+1}S_{j-M,K}
+(-1)^M \sigma_{M+1,M+1}S_{j-1-M,K}$
$\displaystyle S_{j,K}
=\sum_{k=1}^M (-1)^{k-1} \sigma_{k,M+1} S_{j-k,K}
+(-1)^M \sigma_{M+1,M+1}S_{j-(M+1),K}$
Example
$a^3+a^2 b+ab^2+b^3=(a+b+c)(a^2+b^2+ab)
-(ab+ac+bc)(a+b)+abc$
$a^3=(a+b)a^2-(ab)a$
$a^3=(a+b+c)a^2
-(ab+ac+bc)a+abc$
$\left(a^3+b^3+c^3=(a+b+c)(a^2+b^2+c^2)
-(ab+ac+bc)(a+b+c)+3abc\right)$
Lagrange polynomial type
$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}
=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\end{cases}$
Proof
$f(x)=x^n=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{x-x_j}{x_i-x_j}$
$f^{(m-1)}(x)=(m-1)!S_{n,m}$
$f^{(m-1)}(x)=\begin{cases}0=(m-1)!S_{n,m} & 0\le n\le m-2\\(m-1)!=(m-1)!S_{n,m} & n=m-1\end{cases}$
$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}
=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\\
\displaystyle
\boxed{\sum_{r_1+r_2+\cdots+r_m=n-m+1} x_1^{r_1}x_2^{r_2}\cdots x_m^{r_m}}
& n\ge m
\end{cases}$
$S_{m,m}=\sum a$
$S_{m+1,m}=\sum a^2+\sum ab$
$S_{m+2,m}=\sum a^3+\sum a^2 b+\sum abc$
$S_{m+3,m}=\sum a^4+\sum a^3 b+\sum a^2 b^2+\sum a^2 bc+\sum abcd$
Proof
Let $\displaystyle P(x)=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{x-x_j}{x_i-x_j}=x^n+\left(\prod_{i=1}^m (x-x_i)\right)Q(x)$
such that $P(x_i)=0,~\forall 1\le i\le m$
$\displaystyle P(x)=x^n-\left(x^m+\sum_{i=1}^m (-1)^i\sigma_{i,m} x^{m-i}\right)\left(x^{n-m}+\sum_{j=1}^{n-m}q_j x^{n-m-j}\right)$
where $\deg P(x)=m-1,~\deg Q(x)=n-m$
The coefficient of $x^n,x^{n-1},x^{n-2},\cdots,x^m$ should be 0
i.e. $[x^k]P(x)=0,~\forall m\le k\le n$
And then, $[x^{m-1}]P(x)=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}$
Let $K_j=\min\{j,m\}$
$\begin{cases}
[x^n]P(x)=1-1=0\\
[x^{n-1}]P(x)=-\left(q_1-\sigma_{1,m}\right)=0\\
[x^{n-2}]P(x)=-\left(q_2-\sigma_{1,m} q_1+(-1)^{K_2}\sigma_{K_2,m}\right)=0\\
\vdots\\
\displaystyle [x^m]P(x)=-\left(q_{n-m}+\sum_{k=1}^{K_{n-m}-1} (-1)^k \sigma_{k,m} q_{n-m-k}+(-1)^{K_{n-m}}\sigma_{K_{n-m},m}\right)=0\\
\displaystyle [x^{m-1}]P(x)=-\left(\sum_{k=1}^{K_{n-m+1}-1} (-1)^k \sigma_{k,m} q_{n-m+1-k}+(-1)^{K_{n-m+1}}\sigma_{K_{n-m+1},m}\right)\end{cases}$
As $\displaystyle \boxed{S_{j,m}+\sum_{k=1}^{K_j-1} (-1)^k \sigma_{k,m} S_{j-k,m}+(-1)^{K_j}\sigma_{K_j}=0}$
$\begin{cases}
S_{1,m}-\sigma_{1,m}=0\\
S_{2,m}-\sigma_{1,m} S_{1,m}+(-1)^{K_2}\sigma_{K_2,m}=0\\
\vdots\\
\displaystyle S_{n-m,m}+\sum_{k=1}^{K_{n-m}-1} (-1)^k \sigma_{k,m} S_{n-m-k,m}+(-1)^{K_{n-m}}\sigma_{K_{n-m},m}=0\\
\displaystyle S_{n-m+1,m}+\sum_{k=1}^{K_{n-m+1}-1} (-1)^k \sigma_{k,m} S_{n-m+1-k,m}+(-1)^{K_{n-m+1}}\sigma_{K_{n-m+1},m}=0\end{cases}$
$q(m,k)=S_{k,m},~\forall 1\le k\le n-m$
$[x^{m-1}]P(x)=-\left(-S_{n-m+1,m}\right)=S_{n-m+1,m}$ |
|
