A sequence polynomial $P_n(x)$ Given the polynomial sequence $(P_n(x))$ satisfying
$$P_0(x)=P_1(x)=1$$
$$P_{n+2}(x)=P_{n+1}(x)+xP_n(x)$$
Find $P_n(x)$
I know $P_n(x)=\sum_{k\ge 0} {n-k\choose k}x^k$ but don't know how to solve it
Thanks
 A: Note that when $x = 1$ you obtain a Fibonacci's sequence. So you can basically solve this problem using any method that works for solving Fibonacci's recurrence (and there are by now dozens of those). For example, write
$$A = \pmatrix{0 & 1 \cr x & 1}.$$
and observe that 
$$\pmatrix{p_{n+1}(x) \cr p_{n+2}(x)} = A \pmatrix{p_n(x) \cr p_{n+1}(x)}.$$
Now you can iterate this formula to obtain
$$\pmatrix{p_{n}(x) \cr p_{n+1}(x)} = A^n \pmatrix{p_0(x) \cr p_1(x)}.$$
So the problem is reduced to computing the powers of $A$. This in turn can be solved by finding the eigenvalues of $A$ (which amounts here to solving a quadratic equation) and diagonalizing the matrix. See Jordan normal form.
I do not claim this is the easiest way here but this is very useful for solving general recurrence problems. In your case, it's enough to write couple of terms of the sequence, guess the correct solution and then conclude using induction.
A: The standard method for solving difference equations of this sort is to use the Ansatz $p_n=\lambda^n$ which, in this case, leads to the quadratic equation $\lambda^2=\lambda+x$ with solutions $\lambda = \frac 12 (1\pm (4 x + 1)^{\frac 12})$.  Taking the initial values into account gives
$$ P_n(x)=\left (\frac 12 \right )^{n+1}\frac 1 {(4x+1)^{\frac 12}}\left ( (1+(4x+1)^{\frac 12})^{n+1}-(1-(4 x+1)^{\frac 12})^{n+1}\right ) ,$$
(the square root terms cancel).
It is then easy to give an explicit representation as a combination of powers of $x$  by using the binomial theorem
A: Since you knew the answer you could use induction (and Pascal's rule).
