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.

I am wondering how to solve a recurrence of this type

$$p_1(x) = x$$ $$p_2(x) = 1-x^2$$

and

$$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x).$$

I am wondering, how could one solve such a recurrence. One way would be to pretend $x$ is fixed and solve it using the well known method for linear recurrences. My problem with this is that it gets rather messy and besides when solving for the initial terms one gets a fraction that is not well defined for all $x$.

I would therefore like to ask if there is an easier way to solve it or perhaps whats the proper way to apply the theory of linear recurrences.

Edit. The recurrence is indeed of second order.

share|improve this question
    
Because the order of the recurrence equation is 4, you need two more initial conditions for the problem to be well posed. –  Sasha Aug 16 '12 at 19:07
    
Are you sure the recurrence form is not: $$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x)$$ –  S4M Aug 16 '12 at 19:56
    
You have a forth order recurrence relation with constant coefficients which can be solved in a closed form. If you feed this to Maple you will get the answer. –  Mhenni Benghorbal Aug 16 '12 at 20:00
    
@S4M You are right, the recurrence is indeed of this form! –  Jernej Aug 16 '12 at 20:49
add comment

4 Answers 4

up vote 4 down vote accepted

related problem: I, II. Here is the solution of the corrected recurrence relation computed by maple

$$ \left( -3\,x-\sqrt {{x}^{2}+4} \right)\left( -2\, \left( -x-\sqrt{{x}^{2}+4} \right)^{-1} \right) ^{n}{\frac {1}{\sqrt {{x}^{2}+4}}}\left( -x-\sqrt {{x}^{2}+4} \right)^{-1} $$ $$+ \left( 3\,x-\sqrt {{x}^{2}+4} \right)\left( -2\,\left( -x+\sqrt {{x}^{2}+4} \right)^{1} \right) ^{n}{\frac {1}{\sqrt {{x}^{2}+4}}} \left( -x+\sqrt {{x}^{2}+4}\right)^{-1}$$

If you are interested in how you can solve it. Assume your solution $p_n = r^n\,, $ for some $r$ to be determined and substitute in your recurrence relation which gives

$$ r^{n+2} + x r^{n+1} - r^n = 0 \Rightarrow r^n(r^2+xr-1)=0 \Rightarrow (r^2+xr-1)=0$$ $$ r_1 = -\frac{1}{2}\,x+\frac{1}{2}\sqrt {{x}^{2}+4}\,, \,\,\, \, r_2 = -\frac{1}{2}\,x - \frac{1}{2}\,\sqrt {{x}^{2}+4} $$ Now, you construct the general solution as $$ p_n(x) = c_1 {r_{1}}^n + c_2 {r_{2}}^n = c_1 {\left( -\frac{1}{2}\,x+\frac{1}{2}\sqrt {{x}^{2}+4} \right)}^n + {\left( -\frac{1}{2}\,x - \frac{1}{2}\,\sqrt {{x}^{2}+4} \right)}^n $$ To determine the constants $c_1$ and $c_2$, you just need to exploit the initial conditions $p_0(x)$ and $p_1(x)$ and solve for $c_1$ and $c_2$.

share|improve this answer
add comment

I tried another generating function approach for $p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x)$ and did not realize until I got an obviously wrong answer why the method was wrong.

You lucky readers might enjoy finding out why the method was wrong.

Let $F(x) =\sum_{n=1}^{\infty} x^n p_n(x) $. Since $0 = p_{n+2}(x) +xp_{n+1}(x)-p_{n}(x)$, I will try to get $0 = \sum_{n=1}^{\infty} x^n(p_{n+2}(x) +xp_{n+1}(x)-p_{n}(x))$ in terms of $F(x)$ so as to get a formula for $F(x)$.

$\begin{align} \sum_{n=1}^{\infty} x^n p_{n+2}(x) &=x^{-2}\sum_{n=1}^{\infty} x^{n+2} p_{n+2}(x)\\ &=x^{-2}\sum_{n=3}^{\infty} x^{n} p_{n}(x)\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+\sum_{n=1}^{\infty} x^{n} p_{n}(x))\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+F(x))\\ \end{align} $

$\begin{align} \sum_{n=1}^{\infty} x^n (xp_{n+1}(x)) &=\sum_{n=1}^{\infty} x^{n+1} p_{n+1}(x)\\ &=\sum_{n=2}^{\infty} x^{n} p_{n}(x)\\ &=-xp_1(x)+\sum_{n=1}^{\infty} x^{n} p_{n}(x)\\ &=-xp_1(x)+F(x)\\ \end{align} $

Therefore

$\begin{align} 0 &=\sum_{n=1}^{\infty} x^n(p_{n+2}(x) +xp_{n+1}(x)-p_{n}(x))\\ &=\sum_{n=1}^{\infty} x^np_{n+2}(x) +\sum_{n=1}^{\infty} x^n(xp_{n+1}(x))-\sum_{n=1}^{\infty}x^n p_{n}(x)\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+F(x))+(-xp_1(x)+F(x))-F(x)\\ &=x^{-2}(-xp_1(x)-x^2p_2(x)+F(x))-xp_1(x)\\ &=x^{-2}(-xp_1(x)-x^3p_1(x)-x^2p_2(x)+F(x))\\ &=x^{-2}(-(x+x^3)p_1(x)-x^2p_2(x)+F(x))\\ \end{align} $

so

$\begin{align} F(x) &=(x+x^3)p_1(x)+x^2p_2(x)\\ &=(x+x^3)x+x^2(1-x^2)\\ &=x^2+x^4+x^2-x^4\\ &=2x^2\\ \end{align} $

But this is obviously wrong!!!

Why?

And, can this method be salvaged?

share|improve this answer
add comment

Alternatively, compare your recurrence to known recurrences.
In this case, the Chebyshev polynomials ... result:

$$ p_n(x) = i^{n} \Biggl(4 T_n \biggl(\frac{ix}{2}\biggr) - 3 U_n \biggl(\frac{ix}{2}\biggr)\Biggr) $$

share|improve this answer
add comment

Notice that the recurrence equation is constant coefficients, with respect to $n$. It can be solved using the generating function approach. Multiply both sides of the equation with $t^n$ and sum over $n\geqslant 2$: $$ \sum_{n=2}^\infty t^n p_{n+2} = -x \sum_{n=2}^\infty t^n p_{n+1} + \sum_{n=2}^\infty t^n p_{n-2} $$ Defining $g(t,x) = \sum_{n=0}^\infty t^n p_n(x)$ this translates into: $$ \frac{1}{t^2} \left( g(t,x) - p_0(x) -t p_1(x) -t^2 p_2(x) - t^3 p_3(x) \right) = -\frac{x}{t} \left(g(t,x)-p_0(x) - t p_1(x) - t^2 p_2(x) \right) + t^2 g(t,x) $$ giving: $$ g(t,x) = \frac{1+t x}{1+t x-t^4} \left( p_0(x) + t p_1(x) + t^2 p_2(x) \right) + \frac{t^3}{1+t x-t^4} p_3(x) $$ The general solution $p_n(x)$ is obtained by extracting series coefficient: $$ p_n(x) = [t]^n g(t,x) $$

Here is verification in Mathematica:

enter image description here

share|improve this answer
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.