How to solve $f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$?

Question

How to solve the following recurrence relation

$$f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$$

with the initial conditions $f_{1}(x)=x, f_{2}(x)=x^2-1$?

The answer is that $f(x+\frac{1}{x})=\frac{1-x^{2n+2}}{x^{n}(1-x^2)}$ (it may be wrong).

Answer 1

A hint: Treat this problem the same way you would go at the difference equation $$a_n= \sigma\> a_{n-1}-a_{n-2}\qquad(n\geq3)$$ with some given constant $\sigma$. In your case instead of $\sigma$ you have the variable $x$, and $x$ does also appear in the initial conditions.

Answer 2

You can use a brute force method. Possibly the least elegant solution, but here goes:

Compute $f_n(x)$ for a few $n$:

$$\begin{aligned} &f_1(x) = x\\ &f_2(x) = x^2-1\\ &f_3(x) = x^3-2x\\ &f_4(x) = x^4-3x^2+1\\ &f_5(x) = x^5-4x^3+3x\\ &f_6(x) = x^6-5x^4+6x^2-1\\ &f_7(x) = x^7-6x^5+10x^3-4x\\ &f_8(x) = x^8-7x^6+15x^4-10x^2+1 \end{aligned}$$

Do you recognize the binomial coefficients? Ask yourself if this can be generalized to $$f_n(x) = x^n-\binom{n}{2}x^{n-2}+\binom{n-1}{3}x^{n-4}-\binom{n-2}{4}x^{n-6}+\dots$$

Assume it can and prove it by induction, as follows:

Doublecheck that the initial conditions are met by plugging in $n=1$ and $n=2$. Then calculate $f_{n+1}$ under the above assumption.

$$f_{n+1}(x) = xf_n(x)-f_{n-1}(x)=\\ x\left[ x^n-\binom{n}{2}x^{n-2}+\binom{n-1}{3}x^{n-4}-\binom{n-2}{4}x^{n-6}+\dots \right]-\\\left[ x^{n-1}-\binom{n-1}{2}x^{n-3}+\binom{n-2}{3}x^{n-5}-\binom{n-3}{4}x^{n-7}+\dots \right]=\\ x^{n+1} - \left[\binom{n}{2}+1\right]x^{n-1} + \left[\binom{n-1}{3}+\binom{n-1}{2}\right]x^{n-3}-\left[\binom{n-2}{3}+\binom{n-2}{4}\right]x^{n-5}+\dots\\ = \{\text{Well-known binomial identity, cf. Pascal's triangle}\} = \\ x^{n+1} - \binom{n+1}{2}x^{n-1} + \binom{n}{3}x^{n-3} - \binom{n-1}{4}x^{n-5}+\dots$$

which completes the proof.

Comments:

1. Again, brute force-ish, and not very elegant. Also, the expression for $f_n(x)$ might be possible to simplify significantly.
2. The $\dots$ here and there might need to be taken care of more cautiously.
3. The binomial coefficients outside Pascal's triangle are assumed to be $0$.