Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Sequences and Series > Recurrence Relations > Successive Powers

Recurrence Relation of Successive Powers of a Polynomial Root

What a mouthful!  The gist of this topic is that the successive powers of a root of a polynomial form a sequence that has an simple recurrence relation.

The Puzzle in which the Topic Arose

First, let me tell you the puzzle, from one of my fans, Adi Putra, that gave rise to this topic:

If (4x + 4-x) = 7 then (8x + 8-x) = ...

Let y=2x. Then y2+y-2=7, so y4-7y2+1=0.  The solution to the puzzle, then, will be the sum of y3 and y-3.

Solving the quadratic in y2, we get y2 = 7/2 ± sqrt(45)/2

This presents a tricky problem in itself: we can express y2 in the form a+sqrt(b), where a and b are rational, but can y be expressed in this form?  See Simplifying Nested Radicals for the full explanation, but very briefly, the answer is usually no, but in this case (because the puzzle was contrived, I'm sure) the answer is yes...

If so, then starting with the "plus" root, y = a + sqrt(b), so y2 = a2 + b + 2 a sqrt(b)

Equating the rational and irrational parts, 7/2 = a2 + b, and sqrt(45)/2 = 2 a sqrt(b)

Squaring both sides of the second equation, 45/4 = 4 a2 b

Simplifying the equations, we get the following two equations:

2a2 + 2b = 7
16a2 b = 45

As you can see, a2 and b are interchangeable in these equations, so we get two solutions
a2 = 9/4 and b = 5/4, or vice-versa

Selecting the perfect square, 9/4, as a2, we get a=3/2, and b=5/4, so y=3/2+sqrt(5)/2

The other three roots are -3/2+sqrt(5)/2, 3/2-sqrt(5)/2, and -3/2-sqrt(5)/2, but we can throw away the negative roots because we can be sure y is positive, because it's equal to 2x for some real x, so
y=3/2+sqrt(5)/2  or  y=3/2-sqrt(5)/2

The quadratic that has these roots can be obtained by multiplying (y-r1)(y-r2), where r1 and r2 are the two roots.  In this way, we discover that these are the roots of the polynomial y2-3y+1=0, which is interesting because its coefficients are palindromic (if that's not a word it should be).

For one thing, this means the two roots are reciprocals of one another, so pick either one, and the value of yn+y-n will be the same.

For another thing, this means the recurrence relation that describes the sequence of successive powers of y runs the same way in both directions!

Consider the sequence y0, y1, y2, … where y is a root of ay2+by+c=0

yn = -(b/a)yn-1 - (c/a)yn-2, so each element can be obtained from this linear combination of the previous two.

Similarly,

yn = -(b/c)yn+1 - (a/c)yn+2, so each element can be obtained from this linear combination of the following two.

In this case, the coefficients of the polynomial are symmetrical, 1, -3, 1, so each element is equal to three times the previous one minus the one before that, OR three times the next one minus the one after that.

This symmetry is important, because it means that yn + y-n = 3(yn+1 + y-n-1) - (yn+2 + y-n-2)

Knowing this recurrence relation and any two elements in the sequence will allow us to solve the entire sequence.

We know y2+y-2 = 7, and it's obvious that y0+y-0 = 2, so from the recurrence relation (three times the previous/next element minus the element before/after that) it follows that y1+y-1 = 3.

The rest of the sequence follows: 2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, …  (Sloane's A005248)

Do you want to dig a little deeper?

Whenever I see a problem like this one -- it's simple to express, has a simple solution, yet is surprisingly hard to understand and solve -- I find myself very interested to find a way to generate other similar problems.  In this way, I gain agility in solving problems of this type.

The essential elements of this problem are

 - it has a recurrence relation based on a palindromic polynomial
 - you are given only the sum of the nth and -nth elements of the sequence
 - and you're given essentially the square of one of the roots of that polynomial.

For essentially the same problem with different numbers, just start with a different palindromic polynomial, such as
x2-4x+1=0.  Then you can recast the problem as:

If (4x + 4-x) = 14 then (8x + 8-x) = ...

and the answer will be 52.

Getting from the Polynomial to the Recurrence Relation

In general, when the ratio of successive elements of a geometric sequence s0, s1, s2, ... is a root of a polynomial,

a0 + a1x + a2x2 + ... + anxn = 0

Then the recurrence relation for the sequence is

sm = (1/an) (-an-1sm-1 - an-2sm-2 - ... - a0sm-n)

Getting from the Recurrence Relation to the Polynomial

In general, when the recurrence relation of a sequence is given by

sm = (1/an) (-an-1sm-1 - an-2sm-2 - ... - a0sm-n)

then the ratio of successive elements will approach r, a root of the corresponding polynomial,

a0 + a1x + a2x2 + ... + anxn = 0

Take a look at the Fibonacci Numbers -- Their recurrence relation is

Fm = Fm-1 + Fm-2

which gives the corresponding polynomial

x2-x-1=0

And one of the roots of this polynomial is 1/2+sqrt(5)/2, the Golden Ratio, which is the limit of the ratios of successive Fibonacci numbers.

What if there are multiple real roots?

I don't know, but in my tests, some roots tend to be "attractive", and other roots tend to be "repulsive" -- that is, if you start the sequence with the first two elements exactly equal to the repulsive root, then all successive ratios will be the same.  But if you start the sequence with any other ratio, then the limit of the ratios will tend to the attractive root.

What if there is no real root?

Then the successive ratios will not have a limit.  Try a few examples using a spreadsheet, and you'll see what happens -- the elements go into a repeating pattern, or else they fluctuate wildly, alternating between hugely positive and vastly negative numbers.

Related pages in this website

Simplifying Nested Radicals -- If  y2 = a + sqrt(b), and y has this form as well, then how do you find the "a" and the "b" for y?

Fibonacci Numbers -- whose successive ratios approach the Golden Ratio

Recurrence Relations

Formal Power Series

Generating Function

 

The webmaster and author of this Math Help site is Graeme McRae.