Find $f(n)$ given $f(x)$ for $x<n$.

Question

For some unknown non-negative integers $\{a,b,c\}$, we need to find the value of $a^n+b^n+c^n$ where $n>3$ when we are already given the values of $a^x+b^x+c^x$ for every $x<n$.
Eg.
Let $f(x) = a^x+b^x+c^x$,
Given: $f(1) = 6, f(2) = 14, f(3) = 36$
To find: $f(4)$
Solution: Here $a=1, b=2,c=3$ $\implies f(4) = 98$.
But finding values of $a,b,c$ won't be easy. So is there any way to find $f(n)$ using $f(i)$ for $i<n$?

Answer 1

Consider the equations $$a+b+c-6=0 \tag 1$$ $$a^2+b^2+c^2-14=0 \tag 2$$ $$a^3+b^3+c^3-36=0 \tag 3$$ From $(1)$, eliminate $a$ to get $$a=6 - b - c\tag 4$$ Plug in $(2)$ and expand to get $$2 b^2+2 ( c-6) b+2 c^2-12 c+36=0 \tag 5$$ Solve the quadratic in $b$ and keep the largest root; this gives $$b=\frac{1}{2} \left(\sqrt{-3 c^2+12 c-8}-c+6\right)\tag 6$$ Put the expression of $a,b$ in $(3)$ and expand (this is the unpleasant part) and you should arrive to $$3 c^3-18 c^2+33 c-18=0\tag 7$$ Lucky your are since $c=1$ is a root and $$3 c^3-18 c^2+33 c-18=3(c-1)(c^2-5 c+6)=0\tag 8$$ Now solve the quadratic and get as solutions $c=2$ and $c=3$.

So, because of the symmetry, the function is just $$f(x)=1+2 ^x+3^x\tag 9$$

I suppose that, if you were given four values for $f(x)=a^x+b^x+c^x+d^x$, this would have been a nightmare (may be not doable since, using the same elimination process, $c$ will be the solution of a cubic equation in $d$).

Answer 2

Using Newton's identities in terms of the symmetric polynomials in $3$ variables $e_1=a+b+c$, $e_2=ab+bc+ca$,$e_3=abc$:

$$ e_1 = f(1) = 6\quad \implies \quad e_1 = 6$$ $$ 2 e_2 = e_1 f(1) - f(2) = 6 \cdot 6 - 14 \quad \implies \quad e_2 = 11$$ $$ 3 e_3 = e_2 f(1) - e_1 f(2) + f(3) = 11 \cdot 6 - 6 \cdot 14 + 36 \quad \implies \quad e_3 = 6$$

At this point, it can observed that $a,b,c$ are the roots of $t^3 - 6 t^2 + 11 t - 6 = (t-1)(t-2)(t-3)$ so $\{a,b,c\} = \{1,2,3\}$ and $f(4)=98$.

It is possible, however, to calculate $f(4)$ directly, without solving the polynomial, using another one of Newton's identities:

$$f(4) = e_1 f(3) - e_2 f(2) + e_3 f(1) - e_4 = 6 \cdot 36 - 11 \cdot 14 + 6 \cdot 6 - 0 = 98$$