Fibonacci polynomials The Fibonacci polynomials are defined by the recurrence relation:
$$
F_{n+1}(x)=xF_{n}(x)+F_{n-1}(x)\, .
$$
with $F_1(x)=1$ and $F_2(x)=x$. How can I prove:
$$
F_n(x)=\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \, {n-j-1 \choose j}\, x^{n-2j-1}\, .
$$
 A: A non-inductive way, just to meet OP's tastes. Any sequence $\{a_n\}_{n\geq 1}$ fulfilling
$$ a_{n+1} = x a_n + a_{n+1} $$
has the characteristic polynomial $p(z) = z^2-xz-1$, whose roots are given by $\frac{x\pm\sqrt{x^2+4}}{2} $.
So we have the closed formula:
$$ a_n = \alpha\left(\frac{x+\sqrt{x^2+4}}{2}\right)^n + \beta\left(\frac{x-\sqrt{x^2+4}}{2}\right)^n $$
with $\alpha,\beta$ depending on $a_0,a_1$. In our case $\alpha=\frac{1}{\sqrt{4+x^2}}$ and $\beta=-\frac{1}{\sqrt{4+x^2}}$, so:
$$ a_n = \sum_{k=0}^{n-1}\left(\frac{x+\sqrt{x^2+4}}{2}\right)^k \left(\frac{x-\sqrt{x^2+4}}{2}\right)^{n-1-k}.$$
The coefficient of $x^m$ in $a_n$, that is a binomial coefficient, can be recovered from the last formula or by differentiating $m$ times the closed formula. Anyway, the inductive approach is elegant and way shorter. Still another way is to exploit the generating function:
$$ \sum_{n\geq 0}F_n(x) t^n=\frac{t}{1-xt-t^2} $$
then computing $[x^m]F_n(x)$ as: 
$$[t^n][x^m]\frac{t}{1-xt-t^2}=[t^n]\left(\frac{t}{1-t^2}\right)^{m+1}=[t^{n-m-1}]\frac{1}{(1-t^2)^{m+1}}.$$
Binomial coefficients arise since
$$ \frac{1}{(1-z)^{k+1}} = \sum_{n\geq 0}\binom{n+k}{k}z^n $$
by stars and bars, for instance.
