Fibonacci cycles for finite groups For two elements $A$ and $B$ of a finite group $G$ of order $n$, we may define the Fibonacci cycle $Fib(A,B)$ as the sequence 
$$Fib(A,B) =\{A,B,BA,BAB,BABBA,BABBABAB, \dots \}$$
Here, starting from the third element, each element in the sequence is obtained by applying the group operation to the preceding two elements. 
If $A$ and $B$ are both selected to be the identity element $E$, we get a trivial sequence with period 1: $Fib(E,E) =\{E,E,E, \dots \}$. Any other choice for $A$ and $B$ will lead to a Fibonacci cycle with larger period. For instance, if $G$ is the cyclic group of order 3, with elements $E$, $L$ and $R$, a period 8 Fibonacci sequence results:
$$Fib(E,L) = \{E,L,L,R,E,R,R,L,E,L,\dots \}$$
For groups of order 3 it is not possible to create larger cycles. This follows from the fact that the periods of all non-trivial cycles for a given group of order $n$ add up to $n^2-1$. 
The question now arises: what is the maximum period $\tau_n$ obtainable for finite groups of order $n$? 
 A: I don't think it is reasonable to expect any nice characterization.
Let's consider the following much simpler variant where $Fib(A) = \{ A, A^2, A^4,\dots \}$. i.e. each term is just the square of the last term.
If we take $G = \mathbb{Z}/p\mathbb{Z}$ then the period is just the multiplicative order of $2 \mod p$.  However understanding this order is notoriously difficult, and the question of whether the multiplicative order of $2$ attains its maximal possible value of $p-1$ for infinitely many primes $p$ is a famous open question (Artin's conjecture on primitive roots).
For your question if we again take $G = \mathbb{Z}/p\mathbb{Z}$ now with $p >5$ this amounts to computing the multiplicative order of the roots of $x^2-x-1 =0$ in $\mathbb{F}_{p^2}$. I see no reason why this should be any easier than the above problem.
A: The largest period is given by the class-2 version of the little fermat theorm.  For j(3), it is of this form.
For primes leaving a remainder of 2,3 modulo 5, the period divides p+1 an odd number of times.  For primes ending in 1,4 modulo 5, the period divides p-1 an even number of times. Note for 5, the square-root has a period of 2, and thus the number itself has a cycle of 10.
The fibonacci series described in this question, are at most an even number of this.  This means that on the main, we need to double the value to get it.
The lucas series is the key here.  It is cyclic over a period of the number described above, and can contain at most ½(p-1) or ½(p+1), according to whether p is square relative to the square-root number (here 5). 
Since every fibonacci series consists of a pair of intertwined series of the form t(n+1)=3 t(n)-t(n-1), and this reduces modularly relative to N, you get this rule.
A: An infinitesimal contribution to the answer requested:
It is straightforward to work out the full set of periods for all finite groups of low order. Just a matter of 'stepping through' the group multiplication tables. A complete list up to order 9 following from some manual calculations:


*

*Order 1: Trivial group $E$, periods of cycli: {1}

*Order 2: Cyclic group $C_2$, periods of cycli: {3,1}

*Order 3: Cyclic group $C_3$, periods of cycli: {8,1}

*Order 4: Cyclic group $C_4$, periods of cycli: {6,6,3,1}

*Order 4: Klein 4-group $C_2 \times C_2$, periods of cycli: {3,3,3,3,3,1}

*Order 5: Cyclic group $C_5$ periods of cycli: {20,4,1}

*Order 6: Cyclic group $C_6$, periods of cycli: {24,8,3,1}

*Order 6: Dihedral group $D_6$, periods of cycli: {8,6,6,6,3,3,3,1}

*Order 7: Cyclic group $C_7$, periods of cycli: {16,16,16,1}

*Order 8: Cyclic group $C_8$, periods of cycli: {12,12,12,12,6,6,3,1}

*Order 8: Direct product group $C_4 \times C_2$, periods of cycli: {6,6,6,6,6,6,6,6,6,3,3,3,1}

*Order 8: Dihedral group $D_8$, periods of cycli: {6,6,6,6,6,6,6,6,3,3,3,3,3,1}

*Order 8: Quaternion group $Q_8$, periods of cycli: {6,6,6,6,6,..,3,3,3,1}

*Order 8: Elementary Abelian group $C_2 \times C_2 \times C_2$, periods of cycli: {3,3,..,1}

*Order 9: Cyclic group $C_9$, periods of cycli: {24,24,24,8,1}

*Order 9: Elementary Abelian group $C_3 \times C_3$, periods of cycli: {8,8,..,1}


Up to order 9 the largest periods (indicated in bold) result from cyclic groups, and hence up to this order the periods are identical to the Pisano periods.
