# A Polynomial Recurrence relation

I thought about one relation while doing some other problem -

$\displaystyle f_{n}(x) = x(f_{n-1}(x) + f_{n-2}(x)); \ f_0(x) = 1, f_1(x) = x$

I don't know the general procedure to solve such relations. What I tried is to compare the coefficients on both sides and get a recurrence for each of them.

$[x^{n}]{f_{n}(x)} = [x^{n-1}]{f_{n-1}(x)} + [x^{n-1}]{f_{n-2}(x)}$

$[x^n]{f_{n}(x)} = 1$

Similarly,

$[x^{n-1}]{f_{n}(x)} = [x^{n-2}]{f_{n-1}(x)} + [x^{n-2}]{f_{n-2}(x)}$

$[x^{n-1}]{f_n(x)} = n-1$

Similarly,

$[x^{n-2}]{f_n(x)} = \dfrac{(n-2)(n-3)}{2}$

$[x^{n-3}]{f_n(x)} = \dfrac{(n-4)(n-5)(n-6)}{6}$

Now, a general formula can be found relating coefficients.

$\displaystyle [x^k]{f_n(x)} = \sum_{m}^{n-k}{[x^{k+1}]{f_m(x)}}$

Thus,

$\displaystyle f_n(x) = x^n + \frac{(n-1)}{1!} x^{n-1} + \frac{(n-2)(n-3)}{2!} x^{n-2} + \frac{(n-3)(n-4)(n-5)}{3!} x^{n-3} + \cdots$

You can write it in rising/falling factorial if you like that notation.

This function looks interesting. And I would like to investigate more of its properties but I don't know what/how to search for.

Consider a second variable $y$, and rewrite the sequence as $f_0 = 1$, $f_1 = x$, and $f_n = x f_{n-1} + xyf_{n-2}$. Then each $f_n$ is homogeneous of degree $n$ in $x, y$. Then consider the formal series $f_0 + f_1 + f_2 + \cdots$. By rearranging the terms, you will find that this is a geometric series, equal to $1 + x(1+y) + \big(x(1+y)\big)^2 + \cdots$. If you expand this, you take the homogeneous parts of degree $0, 1, ...$ and specialize to $y=1$ you will find your original sequence. This is also why you get the binomial coefficients which you already found on your own.
Just consider your $$x$$ as a fixed value, and solve the resulting recurrence. You get the generating function $$F(z) = \sum_{n \ge 0} f_n(x) z^n = \frac{1 - x - z}{1 - x z - x z^2}$$. Next step is to expand as partial fractions and read off coefficients. Sadly, the denominator doesn't factor nicely (was to be expected, for $$x = 1$$ this is the shifted Fibonacci recurrence).