BRAINWAVES
IV.  Explorations
A MATHEMATICAL CONJURING TRICK

(THEOREM ON RECURRENCE SEQUENCES)

THE STORY SO FAR

Suppose we have a polynomial f(x) = x d  + a 1 x d-1  + a 2 x d-2  +...+ a d , (1) whose roots are R 1 , R 2 , ...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 1  = R 1  + R 2  +...+ R d s 2  = R 1 2  + R 2 2  +...+ R d 2 ... s n  = R 1 n  + R 2 n  +...+ R d n or in short d s n  =  R k n 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 1 s n-1  - a 2 s n-2  -...- a d s 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 i s 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 2  - x - 1 we have from  (3) a 1  = -1 a 2  = -1 s 1  = -a 1  = 1 s 2  = -a 1 s 1  - 2a 2  = 1 + 2 = 3 after which from  (2) s 3  = s 2  + s 1  = 4 s n  = -a 1 s n-1  - a 2 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 3  - x - 1, we have from  (3) a 1  = 0 a 2  = -1 a 3  = -1 s 1  = -a 1  = 0 s 2  = -a 1 s 1  - 2a 2  = 0 + 2 = 2 s 3  = -a 1 s 2  - a 2 s 1  - 3a 3  = 0 - 0 + 3 = 3 after which from  (2) s 4  = -a 1 s 3  - a 2 s 2  - a 3 s 1  = 0 + 2 + 0 = 2 s n  = -a 1 s n-1  - a 2 s n-2  - a 3 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 1 x d-1  + a 2 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 1 x + a 2 x 2  +...+ a d x d   (6) Step 4: Differentiate g to get g': g' (x) = a 1  + 2a 2 x +...+ da d x d-1 Step 5: Define the rational function G (x) = -g' (x) / g (x) whose terms may be generated by polynomial long division. And, Hey Presto!, it will be found that the series s 1  + s 2 x + s 3 x 2  +...+ s n x n-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 2  - x - 1 yields the Lucas sequence  (4) of s n  terms. The corresponding function g (x) = 1 - x - x 2 has the derivative g' (x) = -1 - 2x The rational function G (x)  =  -g' (x)  =   1 + 2x          g (x) 1 - x - x 2 = 1 + 3x + 4x 2  + 7x 3  + 11x 4  + 18x 5  + 29x 6  +... whose coefficients are also the Lucas sequence  (4). Example 2 Similarly, as noted above, f( x) = x 3  - x - 1 yields the recurrence sequence (5) of s n  terms. The corresponding function g (x) = 1 - x 2  - x 3 has the derivative g '(x) = -2x - 3x 2 The rational function G( x) = -g' (x) =   2x + 3x     g (x) 1 - x 2  - x 3 = 0 + 2x + 3x 2  + 2x 3  + 5x 4  + 5x 5  + 7x 6  + 10x 7  + 12x 8  +... whose coefficients are also the sequence  (5). PROOF, or HOW IT IS DONE Let g (x) = 1 + a 1 x + a 2 x 2  +...+ a d x d  (6 bis) H (x) = s 1  + s 2 x + s 3 x 2  +...+ s n x n-1  +... We have to prove that H (x) = G (x). Now   g (x) H (x) = (1 + a 1 x + a 2 x 2  +...+ a d x d )(s 1  + s 2 x + s 3 x 2  +...+ s n x n-1  +...) = s 1  + (s 2  + a 1 s 1 )x + (s 3  + a 1 s 2  + a 2 s 1 )x 2  +... (7) Consider the cases 1  n  d. The general term of (7) here is (s n  + a 1 s n-1  + a 2 s n-2  +...+ a n-1 s 1 )x n-1 However from  (3) above, for 1  n  d s n  + a 1 s n-1  + a 2 s n-2  +...+ a n-1 s 1  = -na n Hence the general term here is -na n x n-1 . Now consider the cases n > d. Here the general term of  (7) is (s n  + a 1 s n-1  + a 2 s n-2  +...+ a d s n-d )x n-1 while from  (2) above s n  + a 1 s n-1  + a 2 s n-2  +...+ a d s n-d  = 0 Hence the general term here is 0.x n-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 1  - 2a 2 x - 3a 3 x 2  -...- da d x d-1 But g' (x)  =  a 1  + 2a 2 x + 3a 3 x 2  +...+ da d x 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.