Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
According to your answer that you know, $P_{1}(x) = 1 + x$. – user123454321 Jan 9 '13 at 11:32
I would guess the answer correctly and induct it. – user123454321 Jan 9 '13 at 11:33
Here is almost the same problem. – Mhenni Benghorbal Jan 9 '13 at 12:32
up vote 0 down vote accepted

Since you knew the answer you could use induction (and Pascal's rule).

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer
Yes, this works as long as the quadratic equation doesn't have a repeated root. If it does, the matrix given in my answer need not be diagonalizable and the result is more complicated than this. Here it works though, so +1 :) – Marek Jan 16 '13 at 19:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.