Register to reply 
Finding roots to a recursively defined polynomial of degree n 
Share this thread: 
#1
Jan2013, 07:11 AM

P: 7

Hello all,
I have a series of polynomials P(n), given by the recursive formula P(n)=xP(n1)P(n2) with initial values P(0)=1 and P(1)=x. P(2)=xx1=x^{2}1 P(3)=x(x^{2}1)(x)=x^{3}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 


#2
Jan2013, 08:11 AM

P: 234

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
Jan2013, 08:31 AM

P: 828

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
Jan2013, 09:11 AM

P: 828

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


#6
Jan2013, 04:50 PM

P: 688

I don't know about the roots yet, but given that the first polynomials in the sequence look like (in some pythonesque representation)
[tex] P(n) = \sum_{k=0}^{\lfloor \frac n 2 \rfloor} (1)^k {{nk} \choose k} x^{n2k} [/tex] A proof (hopefully with as little typos as possible) is in the attached PDF. 


#7
Jan2013, 05:48 PM

P: 234

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



#8
Jan2113, 12:19 PM

P: 7

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^{2}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! 


#9
Jan2213, 09:05 AM

P: 894




#10
Jan2213, 11:43 AM

P: 688

P(n) &= xP(n1)  P(n2) \\ &= x\left( xP(n2)  P(n3) \right)  P(n2) \\ &= (x^21)P(n2)  xP(n3) \end{align*}[/tex]if 1 (or 1, for that matter) is a root of P(n3) 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:



#11
Jan2313, 06:15 PM

P: 7

[tex]\begin{align*} P(n) &= xP(n1)  P(n2) \\ &= x\left( xP(n2)  P(n3) \right)  P(n2) \\ &= (x^21)P(n2)  xP(n3) &= (x^3x1)P(n3)(x^21)P(n2) \end{align*}[/tex] and we could continue to extend this procedure to obtain as many repeated roots as we like. 


#12
Jan2313, 06:29 PM

P: 688

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(nk)  P(k1) P(nk1)[/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+1a)  P(a1) P(2a+1a1) = P(a) ~\big( P(a+1)  P(a1) \big)[/tex]so all roots of P(a) are also roots of P(n), where a=(n1)/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^32x) and (x^21) are also one of the P()'s. P.P.S.: Oops, actually I believe your last line at post#11 should read (x^32x)P(n3)(x^21)P(n4). But you got the idea. 


#13
Jan2313, 08:32 PM

P: 7

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
Jan2313, 10:32 PM

P: 894

[tex]P(n) = P(k) P(nk+1)  P(k1) P(nk)[/tex] Furthermore, since A001477 has the relation P(n) = n , we now have the following expression for n: [tex]n = k*(nk+1)  (k1)*(nk)[/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
Jan2913, 02:32 PM

P: 163

An alternate way to find the closed form is through generating functions. Here is a useful link: http://www.wikihow.com/SolveRecurrenceRelations 


#16
Jan3013, 07:54 AM

P: 894




#17
Feb113, 08:24 AM

P: 894




#18
Feb413, 10:16 PM

P: 7

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(n1)P(n2); 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 


Register to reply 
Related Discussions  
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 