a sequence of functions defined by induction

Question

Given a sequence of functions $\{f_k\}$, suppose for any $k\geq 4$,

$$ f_k=f_1f_{k-1}+\frac{1}{2}(f_2-f_1^2)f_{k-2}+(\frac{1}{6}f_1^3-\frac{1}{2}f_1f_2+\frac{1}{3}f_3)f_{k-3}. $$

I want to obtain the general explicit expression of $f_k$ in terms of $f_1, f_2, f_3$. Is it possible?

I have tried the method that $$ f_k-Af_{k-1}-Bf_{k-2}=\lambda(f_{k-1}-Af_{k-2}-Bf_{k-3}) $$ but find that the degree 3 equation of $\lambda$ cannot be solved (always with some square root or cubic root)... Hence I failed.

Answer 1

This is a classical linear recurrence, and the characteristic polynomial is indeed of the third degree.

Unless some simplification occurs in the coefficients, by luck, you can't escape the complexity of Cardano's formulas. You should try to put the polynomial in the depressed form.

Answer 2

This looks astonishingly like some relation derived from the Newton identities for a polynomial $$p(x)=x^3-e_1x^2+e_2x-e_3$$ of degree $3$ where $e_k$ are the elementary symmetric polynomials in the roots $z_1,z_2,z_3$ and the $$f_k=p_k=z_1^k+z_2^k+z_3^k$$ are their power sums. The coefficients of the polynomial can be expressed via power sums

\begin{align} e_1 &= p_1,\\ e_2 &= \frac12(e_1p_1 - p_2) &&= \frac12 ( p_1^2 - p_2 ),\\ e_3 &= \frac13(e_1p_2 - e_2p_1 + p_3) &&= \frac{1}{6} ( p_1^3 - 3 p_1 p_2 + 2 p_3 ) \end{align}

and the iteration equation for the power sums of degree higher than the polynomial degree is \begin{align} p_4 &= e_1p_3 - e_2p_2 + e_3p_1\\ p_5 &= e_1p_4 - e_2p_3 + e_3p_2\\ &\vdots\\ p_k &= e_1p_{k-1}-e_2p_{k-2}+e_3p_{k-3} \end{align} Combined it gives the stated recursion.