Exercise 1.2.3-33 from TAOCP -- Prove a formula by induction. Exercise:
One evening Dr. Matrix discovered some formulas that might even be classed as more remarkable than those of exercise 20: 
$$\frac{1}{(a-b)(a-c)} + \frac{1}{(b-a)(b-c)} + \frac{1}{(c-a)(c-b)}=0$$ 
$$\frac{a}{(a-b)(a-c)} + \frac{b}{(b-a)(b-c)} + \frac{c}{(c-a)(c-b)}=0$$ 
$$\frac{a^2}{(a-b)(a-c)} + \frac{b^2}{(b-a)(b-c)} + \frac{c^2}{(c-a)(c-b)}=1$$ 
$$\frac{a^3}{(a-b)(a-c)} + \frac{b^3}{(b-a)(b-c)} + \frac{c^3}{(c-a)(c-b)}=a+b+c$$ 
Prove that these formulas are a special case of a general law; let $x_1,x_2,…,x_n$ be distinct numbers, and show that
$$\sum_{j=1}^n(\frac{x_j^r}{\prod_{1\le k \le n, k \ne j}(x_j-x_k)}) = 
\begin{cases}
0, & \text{if 0 $\le$r$\lt$ n - 1} \\
1, & \text{if r = n - 1} \\
\sum_{j=1}^nx_j & \text{if r = n}
\end{cases}$$
The answer of book:
This can be proved by induction on n, if we rewrite the formula as
$$\frac{1}{x_n-x_{n-1}} (\sum_{j=1}^{n}\frac{x_j^r(x_j-x_{n-1})}{\prod_{1 \le k \le n, k \ne j }(x_j-x_k)} - 
\sum_{j=1}^{n}\frac{x_j^r(x_j-x_{n})}{\prod_{1 \le k \le n, k \ne j}(x_j-x_k)})$$
Each of these sums now has the form of the original sum, except on n - 1 elements, and the values turn out nicely by induction when $0 \le r \le n - 1$. 
My question:
I can understand that$\sum_{j=1}^{n}\frac{x_j^r(x_j-x_{n})}{\prod_{1 \le k \le n, k \ne j}(x_j-x_k)}$ = original sum on (n - 1) elements, but I can't turn $\sum_{j=1}^n\frac{x_j^r(x_j-x_{n-1})}{\prod_{1 \le k \le n, k \ne j}(x_j-x_k)}$ into anything related to the original sum.

The second expression
$$
\sum_{j=1}^{n}\frac{x_j^r(x_j-x_{n})}{\prod_{1 \le k \le n, k \ne j}(x_j-x_k)}\tag1
$$
can be further simplified. Notice that when $j=n$, the numerator is zero. When $j$ is not $n$, the factor $x_j-x_n$ in the numerator knocks out the corresponding factor from the denominator. Conclude: $x_n$ does not appear in the expression. In other words, (1) involves all the $x$'s except $x_n$.  This is the sense in which the expression (1) is the $n-1$ case of the general formula, and so you can proceed with your induction.
The same argument shows that the first expression involves all the $x$'s except $x_{n-1}$.
