<s>[INST] Remarquable identities $f(n) = \frac{a^n}{(a-b)(a-c)} + \frac{b^n}{(b-a)(b-c)} + \frac{c^n}{(c-a)(c-b)}$ Let $n$ be an integer, and
\begin{equation}
f(n) = \frac{a^n}{(a-b)(a-c)} + \frac{b^n}{(b-a)(b-c)} + \frac{c^n}{(c-a)(c-b)}
\end{equation}
\begin{equation}
g(n) = \frac{(bc)^n}{(a-b)(a-c)} + \frac{(ac)^n}{(b-a)(b-c)} + \frac{(ab)^n}{(c-a)(c-b)}
\end{equation}
We have the following impressive identities, for all $a,b,c$,
\begin{align}
f(0) &= 0 \\ 
f(1) &= 0 \\
f(2) &= 1 \\
f(3) &= a+b+c \\
f(4) &= a^2 + b^2 + c^2 + ab + ac + bc \\
f(5) &= a^3 + b^3 + c^3 + a^2b + a^2c + b^2c + ab^2 + ac^2 + bc^2 \\
f(6) &= a^4 + b^4 + c^4 + a^3b + a^3c + b^3c + ab^3 + ac^3 + bc^3 + a^2bc + ab^2c + abc^2 +a^2b^2 + a^2c^2 + b^2c^2 \\
 \\
g(0) &= 0 \\ 
g(1) &= 1 \\
g(2) &= ab + ac + bc \\
g(3) &= a^2b^2 + a^2c^2 + b^2c^2 + a^2bc + ab^2c + abc^2 \\
g(4) &= a^3b^3 + a^3c^3 + b^3c^3 + a^3b^2c + a^3bc^2 + a^2b^3c + ab^3c^2 + a^2bc^3 + ab^2c^3 + a^2b^2c^2     
\end{align}
which I have verified by plugging the expressions into Wolfram Alpha. It seems that the general form should be, for $n > 2$.
\begin{align}
f(n) &= \sum_{i+j+k = n-2}a^ib^jc^k \\
g(n) &= \sum_{\substack{i+j+k = 2(n-1)\\1\leq i,j,k \leq n-1}}a^ib^jc^k
\end{align}
The questions are :

*

*How to demonstrate the statements for $n$ general using induction. Intuitively, we should use induction, however I do not see the induction step.


*Could we demonstrate the general case without using induction ? There is a link, between these formulas and Vandermondt matrices (see below), would there be a nice demonstration using matrices ?
=======================================================================
I arrived at such identities when working with partial fractions decomposition,
and after some related work I realized that the Vandermondt matrices where almost the inverse of the matrices which appear when we do partial fractions decomposition,
Then I realised that the Vandermondt matrices have very nice inverse :
\begin{equation}
\begin{pmatrix}
1&1 \\
a&b 
\end{pmatrix}
\begin{pmatrix}
-\frac{b}{(a - b)} & \frac{1}{(a - b)} \\
-\frac{a}{(b - a)} & \frac{1}{(b - a)} \\
\end{pmatrix}
= I_{2}
\end{equation}
\begin{equation}
\begin{pmatrix}
1&1&1 \\
a&b&c \\
a^2&b^2&c^2
\end{pmatrix}
\begin{pmatrix}
\frac{b c}{(a - b) (a - c)} & -\frac{b + c}{(a - b) (a - c)} & \frac{1}{(a - b) (a - c)} \\
\frac{a c}{(b - a) (b - c)} & -\frac{a + c}{(b - a) (b - c)} & \frac{1}{(b - a) (b - c)} \\
\frac{a b}{(c - a) (c - b)} & -\frac{a + b}{(c - a) (c - b)} & \frac{1}{(c - a) (c - b)}
\end{pmatrix}
= I_{3}
\end{equation}
\begin{equation}
\begin{pmatrix}
1&1&1&1 \\
a&b&c&d \\
a^2&b^2&c^2&d^2 \\
a^3&b^3&c^3&d^3
\end{pmatrix}
\begin{pmatrix}
-\frac{bcd}{(a - b) (a - c)(a-d)} & \frac{bc + cd + bd}{(a - b) (a - c)(a-d)} &-\frac{b+c+d}{(a - b) (a - c)(a-d)} &  \frac{1}{(a - b) (a - c)(a-d)}\\
-\frac{a cd}{(b - a) (b - c)(b-d)} & \frac{ac + ad + cd}{(b - a) (b - c)(b-d)} & -\frac{a + c + d}{(b - a) (b - c)(b-d)}& \frac{1}{(b - a) (b - c)(b-d)}\\
-\frac{a bd}{(c - a) (c - b)(c-d)} & \frac{ab + ad + bd}{(c - a) (c - b)(c-d)} & -\frac{a + b + d}{(c - a) (c - b)(c-d)}&\frac{1}{(c - a) (c - b)(c-d)}\\
-\frac{a bc}{(d - a) (d - b)(d-c)} & \frac{ab + ac + bc}{(d - a) (d - b)(d-c)} & -\frac{a + b + c}{(d - a) (d - b)(d-c)}&\frac{1}{(d - a) (d - b)(d-c)}
\end{pmatrix}
= I_{4}
\end{equation}
The identities $f(0),f(1), f(2)$ are the last column of the inverse equation for 3-dim matrices. However, it seems that such matrix argument is not sufficient to prove the case for $n$ general, and that many similar identities (the other places in the matrices) should exist.
 [/INST] With respect to your first question, I don't think induction would be a method that is very helpful here. The problem would be to relate different functions $f(n)$. This is more something that asks for generating functions.
\begin{eqnarray}
f(n) 
& = & \frac{a^n}{(a-b)(a-c)} + \frac{b^n}{(b-a)(b-c)} + \frac{c^n}{(c-a)(c-b)} \\ \\
& = & \frac{(a b^n + b c^n + c a^n) - (a^n b + b^n c + c^n a) }{(a-b)(b-c)(c-a)} \\ \\
& = & \frac{(a^n - b^n) c - a b (a^{n-1} - b^{n-1})   - (a - b) c^n}{(a-b)(b-c)(c-a)}
\end{eqnarray}
For $n=0$ and $n=1$ we see from the second line immediately that the numerator will be zero.
So we only need to consider the case $n \geq 2$. The third line tells us that the numerator is a polynomial in $a,b,c$ with all terms of degree $n+1$. In addition to has a factor $(a-b)$, and like-wise due to symmetry it also has a factors $(b-c)$ and $c-a$. It therefore follows that $f(n)$ is a polynomial in $a,b,c$ with all terms of degree $n-2$.
From this point one could in principle assume that the proposed form is correct, multiply with $(a-b)(b-c)(c-a)$, expand everything, and manipulate the sums until the above form is obtained. It is actually not too difficult. There is, however, an easier approach.
Consider the sum $\sum_{n=0}^\infty \epsilon^n f(n)$ in the limit $\epsilon \rightarrow 0$   ( $|\epsilon| \max(|a|,|b|,|c|) < 1$ for which the sum will converge. We then find
\begin{eqnarray}
\sum_{n=0}^\infty \epsilon^n f(n) & = & \sum_{n=0}^\infty \frac{\epsilon^n  a^n}{(a-b)(a-c)} + \sum_{n=0}^\infty \frac{\epsilon^n b^n}{(b-a)(b-c)} + \sum_{n=0}^\infty \frac{\epsilon^n c^n}{(c-a)(c-b)} \\ \\
& = & 
\frac{1}{(a-b)(a-c)(1-\epsilon a)} + \frac{1}{(b-a)(b-c)(1-\epsilon b)} + \frac{1}{(c-a)(c-b)(1-\epsilon c)} \\ \\
& = & \frac{\epsilon^2}{(1-\epsilon a)(1-\epsilon b)(1-\epsilon c)} \\ \\
& = & \epsilon^2 \left( \sum_{k=0}^\infty (\epsilon a)^k \right) \left( \sum_{l=0}^\infty (\epsilon b)^l \right) \left( \sum_{m=0}^\infty (\epsilon c)^m \right) \\ \\
& = & \epsilon^2 \sum_{n=0}^\infty \epsilon^n \sum_{k+l+m=n} a^k b^l c^m \\ \\
& = & \sum_{n=2}^\infty \epsilon^n \sum_{k+l+m=n-2} a^k b^l c^m
\end{eqnarray}
From which it follows that $f(n)$ is the complete homogeneous symmetric polynomial of degree $n-2$, and that $f(0)=f(1)=0$.
In view of the comment by Blue, the results for $g$ follows.
I don't know whether there is formulation by using matrices that is easier.
</s>