Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

3 Answers

up vote 0 down vote accepted

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

share|improve this answer
add comment

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.