Finding roots to a recursively defined polynomial of degree n

In summary: (x - 2) (x + 2) ... 2 4 (x - 1) (x + 1) ... (x - 2) (x + 2) ... 2 2 5 ... (x - 3) (x + 3) (x - 1) (x + 1) (x + 2) ... 2 2 6 ... (x - 3) (x + 3) (x - 1) (x + 1) (x - 2) ... 2 2 2 7 ...
  • #1
Jack Jenkins
6
0
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=x2-1
P(3)=x(x2-1)-(x)=x3-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
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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.
 
  • #4
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.
 
  • #5
When n is even one is a root.
 
  • #6
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.
 

Attachments

  • recurs_poly.pdf
    105.6 KB · Views: 277
  • #7
if you add the coefficients, they add to zero, therefore the root of 1 for even n, porbably +/- 1.
 
  • #8
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+r2and 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!
 
  • #9
coolul007 said:
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
 
  • #10
ramsey2879 said:
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)
 
Last edited:
  • #11
Dodo said:
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.
 
  • #12
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.
 

Attachments

  • recurs_poly_2.pdf
    54.3 KB · Views: 292
Last edited:
  • #13
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!
 
  • #14
Dodo said:
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)).
 
  • #15
Dodo said:
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
 
  • #16
rs1n said:
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.
 
  • #17
Dodo said:
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]
 
Last edited:
  • #18
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
 
  • #19
Good luck, man! :)

Requesting mod to lock the thread.
 

1. What is a recursively defined polynomial?

A recursively defined polynomial is a type of mathematical function where the coefficients of the polynomial depend on previous terms in the polynomial. This means that the polynomial is defined in terms of itself.

2. How is a recursively defined polynomial different from a regular polynomial?

A regular polynomial has a fixed set of coefficients, while a recursively defined polynomial has coefficients that are determined by previous terms in the polynomial.

3. How do you find the roots of a recursively defined polynomial?

To find the roots of a recursively defined polynomial, you can use the same methods as you would for a regular polynomial, such as the quadratic formula or factoring. However, you may need to use recursion to determine the coefficients for each term.

4. Can all recursively defined polynomials be solved for their roots?

Yes, all recursively defined polynomials can be solved for their roots. However, the process may be more complex and require the use of recursion compared to solving a regular polynomial.

5. What are some real-world applications of recursively defined polynomials?

Recursively defined polynomials have applications in fields such as computer science, physics, and economics. They can be used to model complex systems or to analyze data that changes over time.

Similar threads

  • Linear and Abstract Algebra
2
Replies
43
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
888
  • Linear and Abstract Algebra
Replies
13
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
706
  • Linear and Abstract Algebra
Replies
2
Views
852
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • General Math
Replies
14
Views
452
  • Linear and Abstract Algebra
Replies
4
Views
1K
Replies
1
Views
1K
Back
Top