Key Takeaway: The Fibonacci numbers can be used to find the expected number of tosses of a coin until two consecutive heads appear, with their generating function being (1 - x - x 2 ) l for the Fibonacci numbers.

Abstract

FIBONACCI NUMBERS IN COIN TOSSING SEQUENCES 0. Struve, The Universe (Cambridge, Mass.: MIT Press, 1962). Brian Marsden, letter to the author dated 1976. B. A. Read, The Fibonacci Quarterly, Vol. 8 (1970), pp. 428-438. F.X.Byrne, Bull. Amer. Astron. Soc., Vol. 6 (1974), pp. 426-427. L. H. Wasserman, et al. , Bull. Amer. Astron. Soc, Vol. 9 (1977), p. 498. FIBONACCI NUMBERS IN COIN TOSSING SEQUENCES MARK FINKELSTEIN and ROBERT WHITLEY University of California at Irvine, Irvine, CA 92717 The Fibonacci numbers and their generating function appear in a natural way in the problem of computing the expected number [2] of tosses of a fair coin until two consecutive heads appear. The problem of finding the expected number of tosses of a p-coin until k consecutive heads appear leads to clas- sical generalizations of the Fibonacci numbers. First consider tossing a fair coin and waiting for two consecutive heads. Let 0 n be the set of all sequences of H and T of length n which terminate in BE and have no other occurrence of two consecutive heads. Let S n be the num- ber of sequences in 0 n . Any sequence in 0 n either begins with T, followed by a sequence in 0 n -i, or begins with ET followed by a sequence in C n _ 2 . Thus, S n = S n -1 + Sn-2, Si = 0, S 2 Consequently, S n -i = F ny the nth Fibonacci number. termination in n trials is S n /2 n . Letting The probability of Z 2 n^ n > and using the generating function (1 - x - x 2 ) ~ l for the Fibonacci numbers, yields g{x) = x 2 /(1 - x - x 2 ). Hence, the expected number of trials is J2nS n /2 n n = l We generalize this result to the following Tk