# Recurrence Equation with Polynomial Coefficients

As inspired by this question on the problem site Brilliant,

Let $F_n(a,b,c)=a(b-c)^n+b(c-a)^n+c(a-b)^n$

Is it possible to obtain $F_n$ in terms of $F_3, F_2$?

My attempt at a solution is as follows.

Defining $U=\frac{1}{2}\left((a-b)^2+(b-c)^2+(c-a)^2\right), V=(a-b)(b-c)(c-a)$, we have the following recurrence relationship:

$$F_{n+3}=UF_{n+1}+VF_n$$

Let $g(x)$ be the generating function for the sequence ${F_0,F_1,F_2,\dots}$, that is

$$g(x)=\sum_{i=0}^\infty F_ix^i$$

Then (if my working is correct), from the recurrence relation, we can obtain

$$g(x)=\frac{x^2(F_2-F_0U)+xF_1+F_0}{1-x^2U-x^3V}$$

However, at this point of time, I'm not sure how to proceed, since $U,V$ are not simply numbers.

-
You can just go on, your polynomials behave "like numbers" enough for this to work. But the cubic denominator is nasty... What would $F_0$, $F_1$ be here? –  vonbrand Mar 23 '13 at 12:40
To simplify computations, consider 2 seperate sequences of polynomials $A_n, B_n$ satisfying the given recurrence, and such that $A_1=0, A_2=1, A_3=0, B_1=0, B_2=0, B_3=1$. Next solve for $A_n, B_n$ with these initial conditions. Finally, we have $F_n=A_nF_2+B_nF_3$. –  Ivan Loh Mar 23 '13 at 13:21
Though on second thought I suspect that solving the recurrence will give you back the equation defining $F_n$. –  Ivan Loh Mar 23 '13 at 13:28
@vonbrand $F_0=a+b+c, F_1=0$. But how would you treat the polynomials "like numbers" here? The only approach I know of is to attempt to split $g(x)$ into partial fractions, but how exactly do you apply partial fractions to a function in x with polynomial coefficients? –  Vincent Tjeng Mar 23 '13 at 14:06
@VincentTjeng, just like that. It does work, trust me. And I believe IvanLoh is right, you'll probably jst get back what you started with. –  vonbrand Mar 23 '13 at 14:17

The polynom $y^3-Uy-V$ has the roots $a-b, b-c, c-a$.