Quaternions and 2nd order recurrence relations

[Creighton Dement]

Good evening, 

 Corrected signs in the formula (see below)
> tes[(Ex)^n] = (x_0)*tes[(Ex)^{n-1}] + (x_1)*(x_2)*tes[(Ex)^{n-2}], n >
> 2 with tes[(Ex)] = -x_0.


To sum up, there exist floretions a, b such that ab != ba and a^2 = 0. 

This leads to the following products. If a term can be written as aza
for some z, I put term in parenthesis (because tes[aba] = tes{a^2b] = 0,
etc.):

(a + b)^2 = ab + ba + b^2

(a + b)^3 = (aba) + ab^2 + bab + b^2a + b^3

(a + b)^4 = abab + (ab^2a) + ab^3 + baba + bab^2 + b^2ab + b^3a + b^4

(a + b)^5 = (ababa) + abab^2 + ab^2ab + (ab^3a) + ab^4 + 
babab + bab^2a + bab^3 + b^2aba + b^2ab^2 + b^3ab + b^4a + b^5

(a + b)^6 = ababab + (abab^2a) + abab^3 + (ab^2aba) + ab^2ab^2 + ab^3ab
+ (ab^4a) + ab^5 + bababa + babab^2 + bab^2ab + bab^3a + bab^4 + b^2abab
+ b^2ab^2a + b^2ab^3 + b^3aba + b^3ab^2 + b^4ab + b^5a + b^6

(a + b)^7 = (abababa) + ababab^2 + abab^2ab + (abab^3a) + abab^4 +
ab^2abab + (ab^2ab^2a) + ab^2ab^3 + (ab^3aba) + ab^3ab^2 + ab^4ab +
(ab^5a) + ab^6 + bababab + babab^2a + babab^3 + bab^2aba + bab^2ab^2 +
bab^3ab + bab^4a + bab^5 + b^2ababa + b^2abab^2 + b^2ab^2ab + b^2ab^3a +
b^2ab^4 + b^3abab + b^3ab^2a + b^3ab^3 + b^4aba + b^4ab^2 + b^5ab + b^6a
+ b^7


It seems easy to show that the number of terms in the product (a+b)^n is
Fib(n+2). 

Note: I assume this is just a reformulation of "Words with at most 1
consecutive b-letters"
http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=9 . In
addition, notice that counting elements in parenthesis also gives
A000045 (Is this, too, a reformulation of the same property?) and that
Lucas numbers are the diffence between terms in parenthesis and those
not. 

Proof of above: Let num be the number of terms in the product, then: 
num((a + b)^n) = num(a(a + b)^(n-1)) + num(b(a + b)^(n-1)) 
= num(a(a + b)^(n-1)) + num((a + b)^(n-1)) since none of the terms
cancel when multiplied to the left (or right) by b. 

num(a(a + b)^(n-1)) is the number of all terms in the product (a +
b)^(n-1) which begin with b, i.e. the number of terms in the product (a
+ b)^(n-2). Thus, 
num((a + b)^n) = num((a + b)^(n-2)) + num(b(a + b)^(n-1)).

The main point of interest for me at the moment, however, is in the
breakdown of terms in tes[(a + b)^n]  Note that tes is linear and
tes[xy] = tes[yx] for any floretions x,y.  


Using propeties of tes, we have 

tes[(a + b)^7] = tes[b^7] + 7tes[b^6a] + 7tes{b^4aba] + 7tes[b^3ab^2a] +
7tes[b^2ababa] 
Check: Lucas(7) = 29 = 1 + 7 + 7 + 7 + 7

tes[(a + b)^6] = tes[b^6] + 6tes[b^5a] + 6tes[b^3aba] + 3tes[b^2ab^2a] +
2tes[ababab]
Check: Lucas(6) = 18 = 1 + 6 + 6 + 3 + 2

tes[(a + b)^5] = tes[b^5] + 5tes[b^4a] + 5tes[b^2aba]   

tes[(a + b)^4] = tes[b^4] + 4tes[b^3a] + 2tes[baba]   
 
tes[(a + b)^3)] = tes[b^3] + 3tes[b^2a] 


The claim is that if E = .25('i + i' + 'ii' + 'jj' + 'kk' + 'jk' + 'kj'
+ e) and
x = (x_0)'i + (x_1)'j + (x_2)'k then 

tes[(Ex)^n] = -(x_0)tes[(Ex)^(n-1)] - (x_1)(x_2)tes[(Ex)^(n-2)] with
4tes[Ex] = -x_0

Define F = .25('ii' + 'jj' + 'kk' + e) and G = .25('i + i' + 'jk' +
kj'), 
a = Fx. Then E = F + G and the following relations can be easily derived

(Fx)^2 = 0; GxG = -(x_0)G ; tes[(Gx)^n] = (-x_0)^n  ;  tes[GxFx] =
-(x_1)(x_2) ;
tes[Fx] = 0.

Check (using the above relations for tes[(a + b)^n)]): 

tes[(Ex)^3] = tes[(Fx + Gx)^3] =  tes[(Gx)^3] + 3tes[(Gx)^2a]
            = (-x_0)^3 + 3tes[(GxG)xFx]
	    = (-x_0)^3 - 3(x_0)tes[GxFx]
	    = (-x_0)^3 + 3(x_0)(x_1)(x_2)

-(x_0)tes[(Ex)^2] =  -2(x_0)tes[FxGx] - (x_0)tes[(Gx)^2]
                 = 2(x_0)(x_1)(x_2) - (x_0)^3 
		 
-(x_1)(x_2)tes[(Ex)] = (x_0)(x_1)(x_2)		 

So the claim checks for n = 3. But how do we use the above, for example,
to show that it holds for all n? 

Sincerely, Creighton