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.$

Question

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.

Answer 1

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$).

Answer 2

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)$.

Answer 3

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)$.