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 (4^x + 4^-x) = 7 then (8^x + 8^-x) = ...

Let y=2^x. Then y²+y^-2=7, so y⁴-7y²+1=0.  The solution to the puzzle, then, will be the sum of y³ and y^-3.

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

This presents a tricky problem in itself: we can express y² 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 y² = a² + b + 2 a sqrt(b)

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

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

Simplifying the equations, we get the following two equations:

2a² + 2b = 7
16a² b = 45

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

Selecting the perfect square, 9/4, as a², 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 2^x 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-r₁)(y-r₂), where r₁ and r₂ are the two roots.  In this way, we discover that these are the roots of the polynomial y²-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 yⁿ+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 y⁰, y¹, y², … where y is a root of ay²+by+c=0

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

Similarly,

yⁿ = -(b/c)yⁿ⁺¹ - (a/c)yⁿ⁺², 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 yⁿ + y^-n = 3(yⁿ⁺¹ + y^-n-1) - (yⁿ⁺² + y^-n-2)

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

We know y²+y^-2 = 7, and it's obvious that y⁰+y^-0 = 2, so from the recurrence relation (three times the previous/next element minus the element before/after that) it follows that y¹+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 n^th and -n^th 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
x²-4x+1=0.  Then you can recast the problem as:

If (4^x + 4^-x) = 14 then (8^x + 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 s₀, s₁, s₂, ... is a root of a polynomial,

a₀ + a₁x + a₂x² + ... + a_nxⁿ = 0

Then the recurrence relation for the sequence is

s_m = (1/a_n) (-a_n-1s_m-1 - a_n-2s_m-2 - ... - a₀s_m-n)

Getting from the Recurrence Relation to the Polynomial

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

s_m = (1/a_n) (-a_n-1s_m-1 - a_n-2s_m-2 - ... - a₀s_m-n)

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

a₀ + a₁x + a₂x² + ... + a_nxⁿ = 0

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

F_m = F_m-1 + F_m-2

which gives the corresponding polynomial

x²-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 on this website

Simplifying Nested Radicals -- If  y² = 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 the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]