## Finding roots to a recursively defined polynomial of degree n

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
 PhysOrg.com science news on PhysOrg.com >> Intel's Haswell to extend battery life, set for Taipei launch>> Galaxies fed by funnels of fuel>> The better to see you with: Scientists build record-setting metamaterial flat lens
 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.
 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.

## Finding roots to a recursively defined polynomial of degree n

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.
 Recognitions: Gold Member When n is even one is a root.

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
$$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.
Attached Files
 recurs_poly.pdf (105.6 KB, 9 views)
 Recognitions: Gold Member if you add the coefficients, they add to zero, therefore the root of 1 for even n, porbably +/- 1.
 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+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!

Blog Entries: 2
 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

 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\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:
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)

 Quote by Dodo 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.

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.
Attached Files
 recurs_poly_2.pdf (54.3 KB, 2 views)
 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!

Blog Entries: 2
 Quote by Dodo Not yet there, but here is another tiny step. For n >= 2, and for all k such that 0
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)).

 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 $$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

Blog Entries: 2
 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.

Blog Entries: 2
 Quote by Dodo Not yet there, but here is another tiny step. For n >= 2, and for all k such that 0
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$