Finding roots to a recursively defined polynomial of degree n

Jack Jenkins

Hello all,

I have a series of polynomials P(n), given by the recursive formula P(n)=xP(n-1)-P(n-2) with initial values P(0)=1 and P(1)=x.

P(2)=xx-1=x²-1
P(3)=x(x²-1)-(x)=x³-2x
...

I am confident that all of the roots of P(n) lie on the real line. So for P(n), I hope to find these roots. I am particularly interested in the behavior of the roots as n approaches infinity.

Any help on this is truly appreciated. I haven't the tools to do this problem the way it needs to be done.
Jack

coolul007

When n is odd, zero is a root. I will have to crank out more iterations to see a pattern for the coefficients when n is even.

Robert1986

I think this might be Chebyshev polynomials. You could try to find an explicit formula for the nth polynomial. Do you know how to do this? But I'm guessing that there is a better way.

Robert1986

I think an explicit formula is:
[tex]\frac{(x-\sqrt{x^2-4})^n+(x+\sqrt{x^2-4}^n}{2}[/tex]

but I don't think this will help with the roots.

coolul007

When n is even one is a root.

dodo

I don't know about the roots yet, but given that the first polynomials in the sequence look like (in some pythonesque representation)

Code:

0 [1]
1 [1, 0]
2 [1, 0, -1]
3 [1, 0, -2, 0]
4 [1, 0, -3, 0, 1]
5 [1, 0, -4, 0, 3, 0]
6 [1, 0, -5, 0, 6, 0, -1]
7 [1, 0, -6, 0, 10, 0, -4, 0]
8 [1, 0, -7, 0, 15, 0, -10, 0, 1]
9 [1, 0, -8, 0, 21, 0, -20, 0, 5, 0]
10 [1, 0, -9, 0, 28, 0, -35, 0, 15, 0, -1]
11 [1, 0, -10, 0, 36, 0, -56, 0, 35, 0, -6, 0]
12 [1, 0, -11, 0, 45, 0, -84, 0, 70, 0, -21, 0, 1]
13 [1, 0, -12, 0, 55, 0, -120, 0, 126, 0, -56, 0, 7, 0]
14 [1, 0, -13, 0, 66, 0, -165, 0, 210, 0, -126, 0, 28, 0, -1]
15 [1, 0, -14, 0, 78, 0, -220, 0, 330, 0, -252, 0, 84, 0, -8, 0]
16 [1, 0, -15, 0, 91, 0, -286, 0, 495, 0, -462, 0, 210, 0, -36, 0, 1]
17 [1, 0, -16, 0, 105, 0, -364, 0, 715, 0, -792, 0, 462, 0, -120, 0, 9, 0]
18 [1, 0, -17, 0, 120, 0, -455, 0, 1001, 0, -1287, 0, 924, 0, -330, 0, 45, 0, -1]
19 [1, 0, -18, 0, 136, 0, -560, 0, 1365, 0, -2002, 0, 1716, 0, -792, 0, 165, 0, -10, 0]
20 [1, 0, -19, 0, 153, 0, -680, 0, 1820, 0, -3003, 0, 3003, 0, -1716, 0, 495, 0, -55, 0, 1]

and these numbers are binomial coefficients, this suggests the closed form
[tex]
P(n) = \sum_{k=0}^{\lfloor \frac n 2 \rfloor} (-1)^k {{n-k} \choose k} x^{n-2k}
[/tex]
A proof (hopefully with as little typos as possible) is in the attached PDF.

coolul007

if you add the coefficients, they add to zero, therefore the root of 1 for even n, porbably +/- 1.

Jack Jenkins

Thank you all for your constructive comments!

@coolul007, you're right, there do appear to be roots that occur over and over again, not only 0 and ±1 for n odd or even respectively, but for the square roots of certain integer numbers. For example, P(n), n=4,8,12,16 is zero at x=±[itex]\sqrt{2}[/itex]. I'm trying to find as many patterns like this as i can; it may reduce the work of finding roots if some of the roots are just repeats of simpler problems.

@Robert, I checked out the Chebyshev polynomials and the formulas I found look awfully like mine. If those polynomials are solutions to an ODE then it seems reasonable that these polynomial are also a solution to some ODE, and this could give us something to work with (I'll just have to find this ODE).

@Dodo, I'll have to learn a bit more analysis to fully appreciate that!, but it looks like it's possible to find an explicit formula for the polynomial; now the problem is in finding the roots.

If it means anything, x=2+r²and I'm really interested in finding the (positive) values for r. I figured that making the substitution x would simplify the problem but looking at the Chebyshev polynomials and seeing 2 more often than 1 in the recursive formulas of the first and second kind, I'm going to see if it's useful not to change variables.

Thanks again for all the support!

ramsey2879

Quote by coolul007

When n is even one is a root.

Actually, it appears that 1 is a root when n = 3t - 1. 1 is not a root when n = 4

dodo

Quote by ramsey2879

Actually, it appears that 1 is a root when n = 3t - 1. 1 is not a root when n = 4

I think this may be the case. Since[tex]\begin{align*}
P(n) &= xP(n-1) - P(n-2) \\
&= x\left( xP(n-2) - P(n-3) \right) - P(n-2) \\
&= (x^2-1)P(n-2) - xP(n-3)
\end{align*}[/tex]if 1 (or -1, for that matter) is a root of P(n-3) then it is a root of P(n). And since P(2) = x^2 - 1 and has roots 1 and -1, then this is true for n=2,5,8,...

For similar reasons, 0 is a root (as mentioned) for n=1,3,5,7,...

I was wondering if there is a pattern to the factorization of the P(n)'s, which would give a clue to their roots, but haven't put too much effort there yet.

P.S.: If someone feels courageous, here are the "factorizations" that Maxima gives me for n=1 to 20:

Code:

 1                                  x
 
 2                           (x - 1) (x + 1)

                                  2
 3                            x (x  - 2)

                         2            2
 4                     (x  - x - 1) (x  + x - 1)

                                          2
 5                    (x - 1) x (x + 1) (x  - 3)

                  3    2              3    2
 6              (x  - x  - 2 x + 1) (x  + x  - 2 x - 1)

                          2        4      2
 7                    x (x  - 2) (x  - 4 x  + 2)

                               3              3
 8           (x - 1) (x + 1) (x  - 3 x - 1) (x  - 3 x + 1)

                  2            2            4      2
 9            x (x  - x - 1) (x  + x - 1) (x  - 5 x  + 5)

       5    4      3      2              5    4      3      2
10   (x  - x  - 4 x  + 3 x  + 3 x - 1) (x  + x  - 4 x  - 3 x  + 3 x + 1)

                              2        2        4      2
11        (x - 1) x (x + 1) (x  - 3) (x  - 2) (x  - 4 x  + 1)

       6    5      4      3      2
12   (x  - x  - 5 x  + 4 x  + 6 x  - 3 x - 1)
                                 6    5      4      3      2
                               (x  + x  - 5 x  - 4 x  + 6 x  + 3 x - 1)

         3    2              3    2              6      4       2
13   x (x  - x  - 2 x + 1) (x  + x  - 2 x - 1) (x  - 7 x  + 14 x  - 7)

                       2            2            4    3      2
14   (x - 1) (x + 1) (x  - x - 1) (x  + x - 1) (x  - x  - 4 x  + 4 x + 1)
                                               4    3      2
                                             (x  + x  - 4 x  - 4 x + 1)

            2        4      2        8      6       4       2
15      x (x  - 2) (x  - 4 x  + 2) (x  - 8 x  + 20 x  - 16 x  + 2)

       8    7      6      5       4       3       2
16   (x  - x  - 7 x  + 6 x  + 15 x  - 10 x  - 10 x  + 4 x + 1)
                        8    7      6      5       4       3       2
                      (x  + x  - 7 x  - 6 x  + 15 x  + 10 x  - 10 x  - 4 x + 1)

                         2        3              3
17   (x - 1) x (x + 1) (x  - 3) (x  - 3 x - 1) (x  - 3 x + 1)
                                                   6      4      2
                                                 (x  - 6 x  + 9 x  - 3)

       9    8      7      6       5       4       3       2
18   (x  - x  - 8 x  + 7 x  + 21 x  - 15 x  - 20 x  + 10 x  + 5 x - 1)
                9    8      7      6       5       4       3       2
              (x  + x  - 8 x  - 7 x  + 21 x  + 15 x  - 20 x  - 10 x  + 5 x + 1)

         2        2            2            4      2
19   x (x  - 2) (x  - x - 1) (x  + x - 1) (x  - 5 x  + 5)
                                                  8      6       4       2
                                                (x  - 8 x  + 19 x  - 12 x  + 1)

                       3    2              3    2
20   (x - 1) (x + 1) (x  - x  - 2 x + 1) (x  + x  - 2 x - 1)
           6    5      4      3      2
         (x  - x  - 6 x  + 6 x  + 8 x  - 8 x + 1)
           6    5      4      3      2
         (x  + x  - 6 x  - 6 x  + 8 x  + 8 x + 1)

Jack Jenkins

Quote by Dodo

I think this may be the case. Since[tex]\begin{align*}
P(n) &= xP(n-1) - P(n-2) \\
&= x\left( xP(n-2) - P(n-3) \right) - P(n-2) \\
&= (x^2-1)P(n-2) - xP(n-3)
\end{align*}[/tex]if 1 (or -1, for that matter) is a root of P(n-3) then it is a root of P(n). And since P(2) = x^2 - 1 and has roots 1 and -1, then this is true for n=2,5,8,...

For similar reasons, 0 is a root (as mentioned) for n=1,3,5,7,...

to extend further,
[tex]\begin{align*}
P(n) &= xP(n-1) - P(n-2) \\
&= x\left( xP(n-2) - P(n-3) \right) - P(n-2) \\
&= (x^2-1)P(n-2) - xP(n-3)
&= (x^3-x-1)P(n-3)-(x^2-1)P(n-2)
\end{align*}[/tex]

and we could continue to extend this procedure to obtain as many repeated roots as we like.

dodo

Not yet there, but here is another tiny step.

For n >= 2, and for all k such that 0<k<n. it is not hard to prove (by induction on k - see attached PDF) that[tex]P(n) = P(k) P(n-k) - P(k-1) P(n-k-1)[/tex]For an illustrative example,[tex]\begin{align*}
P(7) &= P(1)P(6) - P(0)P(5) \\
&= P(2)P(5) - P(1)P(4) \\
&= P(3)P(4) - P(2)P(3) \\
&= P(4)P(3) - P(3)P(2) \\
&= P(5)P(2) - P(4)P(1) \\
&= P(6)P(1) - P(5)P(0)
\end{align*}[/tex](The equalities below the middle of this list are just mirrored copies of the equalities above... so nothing new beyond the middle of the list.)

This may be useful because it tells you, for example, that the roots common to P(1) and P(5) (if any) will also be roots of P(7).

Also, notice how P(3) eventually appeared as a common term: all roots of P(3) are also roots of P(7).

This last statement can be generalized. If n is odd, say, n=2a+1, and if you take k=a, you have[tex]P(n) = P(a) P(2a+1-a) - P(a-1) P(2a+1-a-1) = P(a) ~\big( P(a+1) - P(a-1) \big)[/tex]so all roots of P(a) are also roots of P(n), where a=(n-1)/2.

---

P.S.: Ah, Jack, you posted while I was editing. What I did is just an extension of what you posted... if you notice that the polynomials that you begin to build next to each P() --in your post, (x^3-2x) and (x^2-1)-- are also one of the P()'s.

P.P.S.: Oops, actually I believe your last line at post#11 should read (x^3-2x)P(n-3)-(x^2-1)P(n-4). But you got the idea.

Jack Jenkins

Oops indeed! Math and the flu don't mix well. Once I'm feeling better I'll run through some more possibilities using the "family" of equalities above; I bet that there are other ways to represent P(n) as some easily tractable formula of "smaller" P(n)'s.

Unfortunately, it seems that we're left with the problem that while some of the roots carry over, new roots are always being generated when you ascend to a higher n. the problem of finding some way of representing an arbitrarily large P(n) will take arbitrarily large computing capacity. This problem is not very friendly!

ramsey2879

Quote by Dodo

Not yet there, but here is another tiny step.

For n >= 2, and for all k such that 0<k<n. it is not hard to prove (by induction on k - see attached PDF) that[tex]P(n) = P(k) P(n-k) - P(k-1) P(n-k-1)[/tex]For an illustrative example,[tex]\begin{align*}
P(7) &= P(1)P(6) - P(0)P(5) \\
&= P(2)P(5) - P(1)P(4) \\
&= P(3)P(4) - P(2)P(3) \\
&= P(4)P(3) - P(3)P(2) \\
&= P(5)P(2) - P(4)P(1) \\
&= P(6)P(1) - P(5)P(0)
\end{align*}[/tex](The equalities below the middle of this list are just mirrored copies of the equalities above... so nothing new beyond the middle of the list.)

This may be useful because it tells you, for example, that the roots common to P(1) and P(5) (if any) will also be roots of P(7).

Also, notice how P(3) eventually appeared as a common term: all roots of P(3) are also roots of P(7).

This last statement can be generalized. If n is odd, say, n=2a+1, and if you take k=a, you have[tex]P(n) = P(a) P(2a+1-a) - P(a-1) P(2a+1-a-1) = P(a) ~\big( P(a+1) - P(a-1) \big)[/tex]so all roots of P(a) are also roots of P(n), where a=(n-1)/2.

---

P.S.: Ah, Jack, you posted while I was editing. What I did is just an extension of what you posted... if you notice that the polynomials that you begin to build next to each P() --in your post, (x^3-2x) and (x^2-1)-- are also one of the P()'s.

P.P.S.: Oops, actually I believe your last line at post#11 should read (x^3-2x)P(n-3)-(x^2-1)P(n-4). But you got the idea.

I find this tiny step to be an interesting relationship. I went to OEIS and found that most of the sequences with x = 1,2,3...8 start with P(0) = 0, P(1) = 1, P(2) = x. They are respectively the OEIS sequences A128834, A001477, A001906, A001353, A004254, A001109, A004187 and A001090. Given the offset with P(0) = 0 the relationship becomes

[tex]P(n) = P(k) P(n-k+1) - P(k-1) P(n-k)[/tex]

Furthermore, since A001477 has the relation P(n) = n , we now have the following expression for n:

[tex]n = k*(n-k+1) - (k-1)*(n-k)[/tex]

In the formula section in the OEIS pages for the specific values of x noted above there are some formulas that might be true also for all x in general, but none of the sequences that I checked (x=6,3,4) gave the tiny step relation for P(n) (aka a(n)).

rs1n

Quote by Dodo

I don't know about the roots yet, but given that the first polynomials in the sequence look like (in some pythonesque representation)

Code:

0 [1]
1 [1, 0]
2 [1, 0, -1]
3 [1, 0, -2, 0]
4 [1, 0, -3, 0, 1]
5 [1, 0, -4, 0, 3, 0]
6 [1, 0, -5, 0, 6, 0, -1]
7 [1, 0, -6, 0, 10, 0, -4, 0]
8 [1, 0, -7, 0, 15, 0, -10, 0, 1]
9 [1, 0, -8, 0, 21, 0, -20, 0, 5, 0]
10 [1, 0, -9, 0, 28, 0, -35, 0, 15, 0, -1]
11 [1, 0, -10, 0, 36, 0, -56, 0, 35, 0, -6, 0]
12 [1, 0, -11, 0, 45, 0, -84, 0, 70, 0, -21, 0, 1]
13 [1, 0, -12, 0, 55, 0, -120, 0, 126, 0, -56, 0, 7, 0]
14 [1, 0, -13, 0, 66, 0, -165, 0, 210, 0, -126, 0, 28, 0, -1]
15 [1, 0, -14, 0, 78, 0, -220, 0, 330, 0, -252, 0, 84, 0, -8, 0]
16 [1, 0, -15, 0, 91, 0, -286, 0, 495, 0, -462, 0, 210, 0, -36, 0, 1]
17 [1, 0, -16, 0, 105, 0, -364, 0, 715, 0, -792, 0, 462, 0, -120, 0, 9, 0]
18 [1, 0, -17, 0, 120, 0, -455, 0, 1001, 0, -1287, 0, 924, 0, -330, 0, 45, 0, -1]
19 [1, 0, -18, 0, 136, 0, -560, 0, 1365, 0, -2002, 0, 1716, 0, -792, 0, 165, 0, -10, 0]
20 [1, 0, -19, 0, 153, 0, -680, 0, 1820, 0, -3003, 0, 3003, 0, -1716, 0, 495, 0, -55, 0, 1]

and these numbers are binomial coefficients, this suggests the closed form
[tex]
P(n) = \sum_{k=0}^{\lfloor \frac n 2 \rfloor} (-1)^k {{n-k} \choose k} x^{n-2k}
[/tex]
A proof (hopefully with as little typos as possible) is in the attached PDF.

An alternate way to find the closed form is through generating functions. Here is a useful link:

http://www.wikihow.com/Solve-Recurrence-Relations

ramsey2879

Quote by rs1n

An alternate way to find the closed form is through generating functions. Here is a useful link:

http://www.wikihow.com/Solve-Recurrence-Relations

Yes, but does that closed form solve the op's problem more so than that found by Dodo? I think not! PS it would be interesting if you could show that the two closed forms are equivalent to confirm Dodo's finding.

ramsey2879

Quote by Dodo

Not yet there, but here is another tiny step.

For n >= 2, and for all k such that 0<k<n. it is not hard to prove (by induction on k - see attached PDF) that[tex]P(n) = P(k) P(n-k) - P(k-1) P(n-k-1)[/tex]For an illustrative example,[tex]\begin{align*}
P(7) &= P(1)P(6) - P(0)P(5) \\
&= P(2)P(5) - P(1)P(4) \\
&= P(3)P(4) - P(2)P(3) \\
&= P(4)P(3) - P(3)P(2) \\
&= P(5)P(2) - P(4)P(1) \\
&= P(6)P(1) - P(5)P(0)
\end{align*}[/tex](The equalities below the middle of this list are just mirrored copies of the equalities above... so nothing new beyond the middle of the list.)

This may be useful because it tells you, for example, that the roots common to P(1) and P(5) (if any) will also be roots of P(7).

Also, notice how P(3) eventually appeared as a common term: all roots of P(3) are also roots of P(7).

This last statement can be generalized. If n is odd, say, n=2a+1, and if you take k=a, you have[tex]P(n) = P(a) P(2a+1-a) - P(a-1) P(2a+1-a-1) = P(a) ~\big( P(a+1) - P(a-1) \big)[/tex]so all roots of P(a) are also roots of P(n), where a=(n-1)/2.

---

P.S.: Ah, Jack, you posted while I was editing. What I did is just an extension of what you posted... if you notice that the polynomials that you begin to build next to each P() --in your post, (x^3-2x) and (x^2-1)-- are also one of the P()'s.

P.P.S.: Oops, actually I believe your last line at post#11 should read (x^3-2x)P(n-3)-(x^2-1)P(n-4). But you got the idea.

Also [itex]P_{2n} = P_n^2 - P_{n-1}^2[/itex]. More generally, [itex]P_{n-k}*P_{n+k} = P_{n}^2-P_{k-1}^2[/itex]

Similar Threads for: Finding roots to a recursively defined polynomial of degree n
Thread	Forum	Replies
Roots of a third degree polynomial	Precalculus Mathematics Homework	12
Roots of a fourth degree polynomial	Precalculus Mathematics Homework	15
Proof: a polynomial of degree n has at most n roots.	Calculus & Beyond Homework	30
roots of a polynomial of degree 4	Calculus & Beyond Homework	2
Roots of a 4th degree polynomial	Precalculus Mathematics Homework	5

coolul007 Recognitions: Gold Member	When n is odd, zero is a root. I will have to crank out more iterations to see a pattern for the coefficients when n is even.

Robert1986	I think this might be Chebyshev polynomials. You could try to find an explicit formula for the nth polynomial. Do you know how to do this? But I'm guessing that there is a better way.

Robert1986	Finding roots to a recursively defined polynomial of degree n I think an explicit formula is: [tex]\frac{(x-\sqrt{x^2-4})^n+(x+\sqrt{x^2-4}^n}{2}[/tex] but I don't think this will help with the roots.