<s>[INST] How to solve $f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$? 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).
 [/INST] 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:


*

*Again, brute force-ish, and not very elegant. Also, the expression for $f_n(x)$ might be possible to simplify significantly.

*The $\dots$ here and there might need to be taken care of more cautiously. 

*The binomial coefficients outside Pascal's triangle are assumed to be $0$. 

</s>