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:
$$\frac{(x-\sqrt{x^2-4})^n+(x+\sqrt{x^2-4}^n}{2}$$

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)

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
$$P(n) = \sum_{k=0}^{\lfloor \frac n 2 \rfloor} (-1)^k {{n-k} \choose k} x^{n-2k}$$
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=±$\sqrt{2}$. 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]

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]

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$$\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*}$$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:

 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]

I think this may be the case. Since$$\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*}$$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,
$$\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*}$$

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$$P(n) = P(k) P(n-k) - P(k-1) P(n-k-1)$$For an illustrative example,$$\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*}$$(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$$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)$$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]

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$$P(n) = P(k) P(n-k) - P(k-1) P(n-k-1)$$For an illustrative example,$$\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*}$$(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$$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)$$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


$$P(n) = P(k) P(n-k+1) - P(k-1) P(n-k)$$

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

$$n = k*(n-k+1) - (k-1)*(n-k)$$

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]

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

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
$$P(n) = \sum_{k=0}^{\lfloor \frac n 2 \rfloor} (-1)^k {{n-k} \choose k} x^{n-2k}$$
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]

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]

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$$P(n) = P(k) P(n-k) - P(k-1) P(n-k-1)$$For an illustrative example,$$\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*}$$(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$$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)$$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 $P_{2n} = P_n^2 - P_{n-1}^2$. More generally, $P_{n-k}*P_{n+k} = P_{n}^2-P_{k-1}^2$

 

[Jack Jenkins]

Hi everyone, sorry for the long delay I had the flu!

All better now. I actually managed to get a directed study at my college approved that looks into this problem. What I'm concentrating on are the fact that certain numbers, such as 1, sqrt(2), sqrt(3), and (1+sqrt(5))/2 (the golden ratio) all have the property that the recursive formula P(n)=n*P(n-1)-P(n-2); P(0)=1 and P(1)=n, when n is substituted in for one of these certain numbers (which turn out to be the roots of one or more of the polynomials being discussed in this section), cause P to repeat itself, as in 1,sqrt(2),1,0,-1,-sqrt(2),-1,0,1,sqrt(2),...

Anyway, since I'm going to be doing work on this subject for legit college credit, I'm going to ask that people please keep their work on this to themselves, or at least off this page, for legal reasons. Those who have already given valuable input on this page will be credited; I will contact you personally when the time comes.

Jack

 

[dodo]

Good luck, man! :)

Requesting mod to lock the thread.