Interleaving Fibonacci Numbers 

The sequence of Fibonacci numbers is defined by the initial values f_{0} = 0, f_{1} = 1, and the recurrence f_{n} = f_{n1} + f_{n2}. The first several values are 

_{} 

Notice that the evenordered terms satisfy the relations 

_{} 

and so on. Similarly the oddordered terms satisfy the relations 

_{} 

and so on. One way of proving that this pattern continues is by induction. We know by inspection up to a certain n that consecutive Fibonacci numbers are given by 

_{} 

(Note that this requires f_{1} = f_{2} = 1.) Adding these together, term by term, it follows from the basic Fibonacci recurrence that the next evenordered value in the sequence is 

_{} 

which is of the same form as the previous evenordered term, but with n+1 in place of n. Likewise the next oddordered value in the sequence can be found by adding this expression for f_{2(n+1)} to the preceding expressing for f_{2n+1}, which gives 

_{} 

where we have used the fact that f_{1} = 1. This is of the same form as the previous oddordered term, but with n+1 in place of n, so the induction is complete. There, the interleaving odd and even parts of the Fibonacci numbers satisfy the relations 

_{} 

Naturally these identities are closely related to the generating functions for the recurrence relations. We know the ratios of successive values of fn asymptotically approach successive powers of the dominant root f of the characteristic equation x^{2} – x – 1 = 0. Therefore, with n = 6, the evenordered relation approaches 

_{} 

and if we divide this by f^{10} we get 

_{} 

Taking this to the limit as n goes to infinity, and substituting for the derivative of the geometric series, we get 

_{} 

which is equivalent to the characteristic equation f^{2} – f – 1 = 0. However, this isn’t the only possible expansion of the terms of the even (or odd) ordered Fibonacci sequences. For example, given the evenordered sequence 0, 1, 3, 8, 21, 55, 144, … we could simply apply the “greedy algorithm” by expressing each term as the sum of the maximum number of the immediately preceding terms. Thus we have 

_{} 

From this it’s easy to see that f_{2n} = f_{2(n1)} – f_{2(n2)} + 2f_{2(n1)}, so the evenordered Fibonacci numbers satisfy the recurrence 

_{} 

which has the characteristic equation 

_{} 

This shows that another way of arriving at the recurrence for the kth Fibonacci numbers is to solve for the (k2)th degree polynomial that gives, when multiplied by the characteristic polynomial of the Fibonacci sequence, a polynomial whose only nonzero coefficients are for powers that are multiples of k. For example, to find the recurrence for every third Fibonacci number, we evaluate the product 

_{} 

We need the coefficients of x^{5}, x^{4}, x^{2}, and x to vanish, so we require A = 1, B = 2, C = 1, and D = 1. Hence the characteristic polynomial for every third Fibonacci number is 

_{} 

with the corresponding recurrence relation 

_{} 

Naturally the same type of relations can be derived for any linear recurring sequence. For example, consider the “tribonacci” sequence, defined by the initial values t_{0} = t_{1} = t_{2} = 1, and the recurrence t_{n} = t_{n1} + t_{n2} + t_{n3}. The first several values are shown below. 

_{} 

To find the recurrence formula for every third term of this sequence, we can apply the greedy algorithm to express the terms 1, 9, 57, 355, 2209, 13745, 85525, … as follows 

_{} 

From this it’s easy to see that t_{3n} = t_{3(n}_{1)} – 5t_{3(n}_{2)} + t_{3(n}_{3)} + 6t_{3(n}_{1)}, so we have the recurrence 

_{} 

corresponding to the characteristic polynomial 

_{} 

We can relate this back to the greedy recurrence by examining the asymptotic expression in terms of the dominant root f, which can be written in the form 

_{} 

This implies that f is a root of the characteristic polynomial, as expected. Incidentally, the “poles” of this recurrence are 0 and the cube roots of 1. 
