# Showing an indentity with a cyclic sum

Let $$n\geqslant2$$, and $$k\in \mathbb{N}$$

Let $$z_1,z_2,..,z_n$$ be distinct complex numbers

Prove that

$$\sum_{i=1}^{n}\frac {{z}_{i}^{n-1+k}} { \prod \limits_{\substack{j = 1\\j \ne i}}^{ n }{ (z_i-z_j) } } =\large\sum_{i_1+i_2+...+i_n=k}^{ } {z}_{1}^{{i}_{1}} {z}_{2}^{{i}_{2}}...{z}_{n}^{{i}_{n}}$$

This originates from a problem involving Vandermonde 's determinant.

I've tried induction on $$n$$ and $$k$$ without success...

• Your expression following "I rewrote is as:" is wrong, because $\prod z_i^k=z_i^{(n-1)k}\ne z_i^{n-1+k}$.
– Hans
Jul 27, 2014 at 19:41
• @Hansen yes, you're right. Jul 28, 2014 at 5:05

The case $n=2$ is simple. If $z_i = 0$ for any $i$ then we can prove it by induction. So we suppose that $z_i \neq 0$ for each $i$.

We choose $R > 0$ such that $|Rz_i| \leqslant 1$ for each $i$. Then $\displaystyle{ \sum_{m=0}^{\infty} (xz_i)^m}$ converges. We have

$\displaystyle{ \prod_{i=1}^n \sum_{m=0}^{\infty} (xz_i)^m = \prod_{i=1}^n \frac{1}{1-xz_i} = \sum_{i=1}^n \frac{A_i}{1-xz_i}}$

for some $A_i$ (analysis in simple fractions). If $z_i = 0$ for any $i$ it is also $A_i = 0$. Otherwise multiplying both side by $(1-xz_i)$ and taking the limits we have

$\displaystyle{ A_i = \lim_{x \to 1/z_i} \prod_{j \neq i} \frac{1}{1-xz_j} = \prod_{j \neq i} \frac{z_i^{n-1}}{z_i-z_j}.}$

So finally we have

$\displaystyle{\prod_{i=1}^n \sum_{m=0}^{\infty} (xz_i)^m = \sum_{i=1}^n \frac{z_i^{n-1}}{(1-xz_i)\prod_{j \neq i}(z_i-z_j)} = \sum_{i=1}^n \frac{z_i^{n-1}}{\prod_{j \neq i}(z_i-z_j)}\sum_{m=0}^{\infty} (xz_i)^m.}$

Now comparing the coefficients of $x^k$ we get the result.

• Wow, great answer! Jul 28, 2014 at 10:37
• Now I feel ridiculous with my complicated pedestrian solution ... Jul 28, 2014 at 18:25
• Very short and Nice answer +1. Feb 3, 2016 at 9:45

I would say here thart the difficulty is more in the notations than in the mathematics. I present below a proof by induction on $n$, where the result for $\lbrace z_1,z_2,\ldots,z_n \rbrace$ is deduced from the result for $\lbrace z_1,z_2,\ldots,z_{n-1} \rbrace$ and the result for $\lbrace z_1,z_2,\ldots,z_{n-2},z_n \rbrace$. This proof, although completely elementary and natural, is full of lengthy formulas on several lines, and I suspect that there are shorter and more elegant proofs.

To ease notation a little, let us put

$$M(n,\lbrace x_1,x_2,\ldots,x_r \rbrace)= \sum_{l_1+l_2+\ldots+l_r}x_1^{l_1}x_2^{l_2}\ldots x_r^{l_r}, \ P(y,\lbrace x_1,x_2,\ldots,x_r \rbrace)= \prod_{k=1}^r\frac{1}{y-x_k} \tag{1}$$

Your identity can then be reformulated as

$$\sum_{i=1}^n z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i})= M(k,\lbrace z_1,z_2,\ldots,z_n \rbrace) \tag{2}$$

Throughout this proof, we shall use freely the following identities, which follow immediately from the definitions in (1) :

$$M(n,X)=\sum_{t=0}^n M(n-t,X\setminus\lbrace x \rbrace)x^t, \ \ \ P(y,X)=\frac{1}{y-x}P(y,X\setminus\lbrace x \rbrace). \tag{3}$$

We prove (2) by induction on $n\geq 2$. When $n=2$, (2) reduces to a familiar and easy identity in $\frac{z_2}{z_1}$. So let us assume $n>2$ and that (2) holds for every $n'<n$. First ,using (2) on the $n-1$-element set $\lbrace z_1,z_2,\ldots,z_{n-2},z_n\rbrace$, we have

$$\Bigg(\sum_{i=1}^{n-2} z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i,j\neq n-1})\Bigg)+ z_n^{k+n-1}P(z_n,\lbrace z_j\rbrace_{j\leq n-2})= M(k+1,\lbrace z_1,z_2,\ldots,z_{n-2},z_n \rbrace) \tag{4}$$

Or in other words,

$$\Bigg(\sum_{i=1}^{n-2} \frac{z_i^{k+n-1}}{z_i-z_n}P(z_i,\lbrace z_j\rbrace_{j\neq i,j\leq n-2})\Bigg)+ z_n^{k+n-1}P(z_n,\lbrace z_j\rbrace_{j\leq n-2})= \sum_{t=0}^{k+1}M(k+1-t,\lbrace z_1,z_2,\ldots,z_{n-2} \rbrace)z_n^t \tag{5}$$

Divide this by $z_n-z_{n-1}$ :

$$\Bigg(\sum_{i=1}^{n-2} \frac{z_i^{k+n-1}}{(z_i-z_n)(z_n-z_{n-1})} P(z_i,\lbrace z_j\rbrace_{j\neq i,j\leq n-2})\Bigg)+ z_n^{k+n-1}P(z_n,\lbrace z_j\rbrace_{j\leq n-1})= \sum_{t=0}^{k+1}M(k+1-t,\lbrace z_1,z_2,\ldots,z_{n-2} \rbrace)\frac{z_n^t}{z_n-z_{n-1}} \tag{6}$$

Now, each of the terms in (6) can be expanded in its own way : we have

$$\begin{array}{lcl} \frac{1}{(z_i-z_n)(z_n-z_{n-1})} &=& \frac{1}{(z_i-z_{n-1})(z_n-z_{n-1})}+\frac{1}{(z_n-z_{i})(z_{n-1}-z_i)}\\ \frac{z_n^t}{z_n-z_{n-1}} &=& \sum_{s=0}^{t-1}z_{n-1}^{t-1-s}z_n^s+\frac{z_{n-1}^t}{z_n-z_{n-1}}\\ \end{array}\tag{7}$$

whence

$$\begin{array}{l} \frac{z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i,j\leq n-2})}{(z_i-z_n)(z_n-z_{n-1})} \\ = \frac{z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i,j\leq n-2})}{z_n-z_{n-1}}+z_i^{k+n-1} P(z_i,\lbrace z_j\rbrace_{j\neq i})\\ \text{and} \\ \sum_{t=0}^{k+1}M(k+1-t,\lbrace z_1,z_2,\ldots,z_{n-2} \rbrace)\frac{z_n^t}{z_n-z_{n-1}} \\ = M(k,\lbrace z_1,z_2,\ldots,z_n \rbrace)+\frac{M(k+1,\lbrace z_1,z_2,\ldots,z_{n-1} \rbrace)}{z_n-z_{n-1}}\\ \end{array}\tag{8}$$

Injecting (8) into (6), we deduce

$$\begin{array}{l} \Bigg(\sum_{i=1}^{n-2} \frac{z_i^{k+n-1}}{z_n-z_{n-1}}P(z_i,\lbrace z_j\rbrace_{j\neq i,j\leq n-2})\\ +\sum_{i=1}^{n-2} z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i})\Bigg) \\ +z_n^{k+n-1}P(z_n,\lbrace z_j\rbrace_{j\leq n-1})\\ =M(k,\lbrace z_1,z_2,\ldots,z_n \rbrace)+ \frac{M(k+1,\lbrace z_1,z_2,\ldots,z_{n-1} \rbrace)}{z_n-z_{n-1}} \end{array} \tag{9}$$

In other words,

$$\begin{array}{l} \Bigg(\sum_{i\neq n-1}z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i})\Bigg) -M(k,\lbrace z_1,z_2,\ldots,z_n \rbrace) \\ = \\ +\frac{M(k+1,\lbrace z_1,z_2,\ldots,z_{n-1} \rbrace)}{z_n-z_{n-1}}- \Bigg(\sum_{i=1}^{n-2} \frac{z_i^{k+n-1}}{z_{n}-z_{n-1}}P(z_i,\lbrace z_j\rbrace_{j\neq i,j\leq n-2})\Bigg) \end{array} \tag{10}$$

Now, adding $z_{n-1}^{k+n-1}P(z_{n-1},\lbrace z_j\rbrace_{j\neq n-1})= \frac{z_{n-1}^{k+n-1}P(z_{n-1},\lbrace z_j\rbrace_{j\neq n-1,j\neq n})}{z_{n-1}-z_{n}}$ to both sides of this equality, we obtain

$$\begin{array}{l} \Bigg(\sum_{i}z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i})\Bigg) -M(k,\lbrace z_1,z_2,\ldots,z_n \rbrace) \\ = \\ +\frac{M(k+1,\lbrace z_1,z_2,\ldots,z_{n-1} \rbrace)- \sum_{i=1}^{n-1}z_i^{k+n-1}P(z_i,\lbrace z_j\rbrace_{j\neq i,j\leq n-1})}{z_n-z_{n-1}} \end{array} \tag{11}$$

The RHS must be zero by the induction hypothesis, which concludes the proof.