Prove that $\frac{a^n}{(a-b)(a-c)}+\frac{b^n}{(b-a)(b-c)}+\frac{c^n}{(c-a)(c-b)}\in \Bbb Z.$ 
Given $a,b,c\in \Bbb Z$, pairwise distinct, and $n\in \Bbb N\setminus\{0\}$ prove that 
  $$S(n)=\frac{a^n}{(a-b)(a-c)}+\frac{b^n}{(b-a)(b-c)}+\frac{c^n}{(c-a)(c-b)}\in \Bbb Z.$$
Source: tagged as Kurshar 1959 in a text with problems from math contests

My attempt: I approached the problem trying first to solve a particular instance, such as $n=1$, to get some insight. 
In this particular case ($n=1$), the proof is straightforward:
$$S(1)=\frac{a(b-c)-b(a-c)+c(a-b)}{(a-b)(a-c)(b-c)}$$
$$S(1)=\frac{ab-ac-ab+bc+ac-bc}{(a-b)(a-c)(b-c)}=0\in \Bbb Z$$
Then, I tried the avenue of an induction proof, considering that the proposition is true for $S(1)$ so that assuming that it is also true for $S(n-1)$ it would imply it is true for $S(n)$. But I couldn't make this step to work. 
Hints and answers, not necessarily with induction will be appreciated. But if possible with induction, that would be nice. Sorry if this is a dup.
 A: For $n > 1$, $S(n)=\displaystyle\sum_{\substack{n_1, n_2, n_3 \geqslant 0 \\ n_1 + n_2 + n_3 = n - 2}}a^{n_1}b^{n_2}c^{n_3}$ (not the most elegant, but nice I think).
For a motivation: the complete homogeneous symmetric polynomial $h_k(x_1, \ldots, x_n)$, when $x_1, \ldots, x_n$ are pairwise distinct, is equal to $\displaystyle\sum_{i=1}^{n}\frac{x_i^{n+k-1}}{\prod_{j\neq i}(x_i-x_j)}$ (proven by induction on $n$, using the identity $h_k(x_1,\ldots,x_{n+1})=\displaystyle\sum_{d=0}^k h_d(x_1,\ldots,x_n)x_{n+1}^{k-d}$ that holds by the definition of $h_k$).
A: Let $f(x)$ denote the remainder of $x^n$ when divided by $g(x):=(x-a)(x-b)(x-c)$.  Because $g(x)\in\mathbb{Z}[x]$ is monic and $x^n\in\mathbb{Z}[x]$, we conclude that $f(x)\in\mathbb{Z}[x]$.  Observe that $f(x)$ has degree at most $2$ and $f(t)=t^n$ for $t\in\{a,b,c\}$.  We apply Lagrange interpolation to get
$$f(x)=\frac{(x-b)(x-c)}{(a-b)(a-c)}a^n+\frac{(x-c)(x-a)}{(b-c)(b-a)}b^n+\frac{(x-a)(x-b)}{(c-a)(c-b)}c^n\,.$$
Since $f(x)\in\mathbb{Z}[x]$, the coefficient of $x^2$, which is
$$\frac{a^n}{(a-b)(a-c)}+\frac{b^n}{(b-c)(b-a)}+\frac{c^n}{(c-a)(c-b)}\,,$$
must be an integer.
More generally, we also have
$$\sum_{j=1}^k\,\frac{a_j^n}{\prod\limits_{i\in\{1,2,\ldots,k\}\setminus\{j\}}\,\left(a_j-a_i\right)}\in\mathbb{Z}$$
for all pairwise distinct integers $a_1,a_2,\ldots,a_k$.  The prove is similar, by considering $g(x)=\prod\limits_{j=1}^k\,\left(x-a_j\right)$ instead.  Then, the required expression is the coefficient of $x^{k-1}$ in the polynomial $f(x)$ obtained as the remainder when dividing $x^n$ by $g(x)$.
A: Similar to your $S(1)$ case, write 
$$
S(n) = \frac{a^n(b-c) - b^n(a-c) + c^n(a-b)}{(a-b)(a-c)(b-c)}.
$$
Now look at the numerator.
$$
a^n(b-c) - b^n(a-c) + c^n(a-b) = ab(a^{n-1}-b^{n-1}) - c(a^n-b^n) + c^n(a-b).
$$
So $(a-b)$ is a factor of the numerator. By symmetry so should $(b-c)$ and $(c-a)$.
