Question

(5) Fibonacci sequences in groups. The Fibonacci numbers Fn are defined recursively by Fo 0, F1 -1, and Fn - Fn-1+Fn-2 forn 2 2. The definition of this sequence only depends on a binary operation. Since every group comes with a binary operation, we can define Fibonacci- type sequences in any group. Let G be a group, and define the sequence {fn in G as follows: Let ao, a1 be elements of G, and define fo-ao, fi-a1, and fn-an-1an-2 forn 2 2 In his paper "Fibonacci Series Modulo m" (American Mathematical Monthly, Vol. 67, 1960), D.D. Wall writes the following about his introduction to these sequences: "The problem arose in connection with a method for generating random numbers but it turned out to be unexpectedly intricate, and so quickly became of interest in its own right." In an interesting application of Fibonacci sequences in groups, Iannis Xenakis (in Formal- ized Music, Indiana University Press, 1971) uses Fibonacci sequences in groups to create "Fibonacci motions," which are sequences of musical properties such as pitch, volume, and timbre that give the composition its framework. We will see in this problem that these Fi- bonacci sequences become intricate quite quickly. (a) Explain why fn-Fn if GZ, ao 0, and a 1. (b) Find the elements in {fn) if G-Z3, ao 1 and a 2

Answer 1

(a) In the graph G = Z, the binary operation is ordinary addition of integers. So, f_0 = a_0 = 0 = F_0 f = a_1 = F_1 Therefore f_n = a_n - 1 a_n - 2 = a_n - 1 + a_n - 2 = F_n - 1 + F_n - 2 = F_n > n greaterthanorequalto 2 i.e, f_n = F_n, Forall n greaterthanorequalto 2. (b) G = Z_3 a_0 = [1], a_1 = [2]. Therefore f_0 = a_0 = [1] f_1 = a_1 = [2] f_2 = f_0 rightarrow f_1 = [1] + [2] = [0] f_3 = f_1 rightarrow f_2 = [2] + [0] = [2] f_4 = f_2 + f_3 = [0] + [2] = [2] f_5 = f_3 + f_4 = [2] + [2] = [1], f_6 = f_4 + f_5 = [2] + [1] = [0], f_7 = f_5 + f_6 = [1] + [0] = [1], f_8 = f_6 + f_7 = [0] + [1] = [1], f_9 = f_7 + f_8 = [1] + [1] = [2], \r\n Therefore The sequence {f_n} is rightarrow {[1], [2], [0], [2], [1], [0], [1], [1], [2], [0], [2], [2], [1], ....} [The same pattern is repeated again & again. For convenience, I have underlined the group of elements which are being repeated].