Brainwaves - Explorations

BRAINWAVES

IV. Explorations

Home

Booklets and Leaflets

BRAINWAVES Reports

The Three Gospels

Explorations

Bipolarity

Quotations

Odds and Ends

Favourite Websites

A MATHEMATICAL CONJURING TRICK

(THEOREM ON RECURRENCE SEQUENCES)

THE STORY SO FAR

Suppose we have a polynomial

f(x) = x^d + a₁x^d^-1 + a₂x^d^-2 +...+ a_d, (1)

whose roots are R₁, R₂, ...R_d. We can create from these roots a sequence (s_n), each of whose terms s_n is the sum of their nth powers (integer n). Thus

s₁ = R₁ + R₂ +...+ R_d

s₂ = R₁² + R₂² +...+ R_d²

...

s_n = R₁ⁿ + R₂ⁿ +...+ R_dⁿ

or in short

s_n = Σ R_kⁿ

k=1

This is an integer for n ≥ 0, and for all n if a_d = ±1.

The terms of any (s_n) form a recurrence sequence

s_n = -a₁s_n_-1 - a₂s_n_-2 -...- a_ds_n-d. (2)

(A recurrence sequence is a sequence of numbers in which each term is obtained from its predecessors according to some specified rule. The best known is the Fibonacci sequence 1, 1, 2, 3, 5, 8, ... in which each term is the sum of the previous two.)

The first d terms can be calculated, without knowing the values of R_k, by Newton's formula

n-1

s_n = Σ -a_is_n-i - na_n, (3)

i=1

and the sequence can then be continued indefinitely from (2).

[Note that (2) and (3) are equivalent when n > d since then a_n = 0.]

Example 1

For f(x) = x² - x - 1 we have from (3)

a₁ = -1

a₂ = -1

s₁ = -a₁ = 1

s₂ = -a₁s₁ - 2a₂ = 1 + 2 = 3

after which from (2)

s₃ = s₂ + s₁ = 4

s_n = -a₁s_n_-1 - a₂s_n_-2 = s_n_-1 + s_n_-2

giving the Lucas sequence

1, 3, 4, 7, 11, 18, 29,... (4)

well known for its similarity to the Fibonacci sequence whose rule it shares.

Example 2

For f(x) = x³ - x - 1, we have from (3)

a₁ = 0

a₂ = -1

a₃ = -1

s₁ = -a₁ = 0

s₂ = -a₁s₁ - 2a₂ = 0 + 2 = 2

s₃ = -a₁s₂ - a₂s₁ - 3a₃ = 0 - 0 + 3 = 3

after which from (2)

s₄ = -a₁s₃ - a₂s₂ - a₃s₁ = 0 + 2 + 0 = 2

s_n = -a₁s_n_-1 - a₂s_n_-2 - a₃s_n_-3 = s_n_-2 + s_n_-3

giving the sequence

0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22,... (5)

THE CONJURING TRICK

Step 1:

Choose a polynomial f of the form given in (1):

f(x) = x^d + a₁x^d^-1 + a₂x^d^-2 +...+ a_d

Step 2:

Obtain from f a recurrence sequence (s_n) as explained above.

Step 3:

Reverse the order of the powers in f and call the result g:

g(x) = 1 + a₁x + a₂x² +...+ a_dx^d (6)

Step 4:

Differentiate g to get g':

g'(x) = a₁ + 2a₂x +...+ da_dx^d^-1

Step 5:

Define the rational function

G(x) = -g'(x)/g(x)

whose terms may be generated by polynomial long division.

Flourish:

It will be found that the series

s₁ + s₂x + s₃x² +...+ s_nxⁿ^-1 +...

so generated by G(x) has the same coefficients as the sequence (s_n) obtained from the original function f in Step 2.

Example 1

As noted above, the function

f(x) = x² - x - 1

yields the Lucas sequence (4) of s_n terms. The corresponding function

g(x) = 1 - x - x²

has the derivative

g'(x) = -1 - 2x

The rational function

	G(x)	=	-g'(x)	=	1 + 2x
			g(x)		1 - x - x²

= 1 + 3x + 4x² + 7x³ + 11x⁴ + 18x⁵ + 29x⁶ +...

whose coefficients are also the Lucas sequence (4).

Example 2

Similarly, as noted above,

f(x) = x³ - x - 1

yields the recurrence sequence (5) of s_n terms. The corresponding function

g(x) = 1 - x² - x³

has the derivative

g'(x) = -2x - 3x²

The rational function

	G(x)	=	-g'(x)	=	2x + 3x²
			g(x)		1 - x² - x³

= 0 + 2x + 3x² + 2x³ + 5x⁴ + 5x⁵ + 7x⁶ + 10x⁷ + 12x⁸ +...

whose coefficients are also the sequence (5).

PROOF, or HOW IT IS DONE

Let g(x) = 1 + a₁x + a₂x² +...+ a_dx^d (6 bis)

H(x) = s₁ + s₂x + s₃x² +...+ s_nxⁿ^-1 +...

We have to prove that H(x) = G(x).

Now g(x)H(x)

= (1 + a₁x + a₂x² +...+ a_dx^d)(s₁ + s₂x + s₃x² +...+ s_nxⁿ^-1 +...)

= s₁ + (s₂ + a₁s₁)x + (s₃ + a₁s₂ + a₂s₁)x² +... (7)

Consider the cases 1 ≤ n ≤ d. The general term of (7) here is

(s_n + a₁s_n_-1 + a₂s_n_-2 +...+ a_n_-1s₁)xⁿ^-1

However from (3) above, for 1 ≤ n ≤ d

s_n + a₁s_n_-1 + a₂s_n_-2 +...+ a_n_-1s₁ = -na_n

Hence the general term here is -na_nxⁿ^-1.

Now consider the cases n > d. Here the general term of (7) is

(s_n + a₁s_n_-1 + a₂s_n_-2 +...+ a_ds_n-d)xⁿ^-1

while from (2) above

s_n + a₁s_n_-1 + a₂s_n_-2 +...+ a_ds_n-d = 0

Hence the general term here is 0.xⁿ^-1 = 0.

Hence g(x)H(x) in (7) reduces to a terminating series with d terms of the form -na_n:

g(x)H(x) = -a₁ - 2a₂x - 3a₃x² -...- da_dx^d^-1

But

g'(x) = a₁ + 2a₂x + 3a₃x² +...+ da_dx^d^-1

Hence

g(x)H(x) = -g'(x)

H(x) = -g'(x)/g(x) = G(x)

as required.

COMMENT

The rational function g'(x)/g(x) is of particular mathematical interest since

óg'(x) dx = ln(g(x))

õ g(x)

Its inverse also features in Newton-Raphson iteration.

Martin Mosse,

August 2011.

ACKNOWLEDGEMENTS

The stimulus for this paper came from Reference 1, of which a copy was kindly sent to me by Professor George Spencer-Brown in June 1999.

I wish to acknowledge the help of Dr Watcyn Wynn in providing a rather better proof than I had found myself.

I believe that the theorem, which I found in November 2009, is original and would welcome confirmation of this, or correction if not. Email martin@brainwaves.org.uk .

REFERENCE

1. 'The Identification of Prime Numbers Using Algebraic Numbers of Degree > 2', by J.C.P. Miller, G. Spencer-Brown and D.J. Spencer-Brown; unpublished but distributed by G. Spencer-Brown in 1965.