Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: A MATRIX DYNAMICS APPROACH TO GOLOMB’S RECURSION. | A MATRIX DYNAMICS APPROACH TO GOLOMB S RECURSION Edward J. Barbeau John Chew and Stephen Tanny Department of Mathematics University of Toronto Toronto ON M5S 3G3 barbeau@ jjchew@ and tanny@ Submitted February 10 1997 Accepted July 14 1997 Abstract In an unpublished note Golomb proposed a family of strange recursions of metahbonacci type parametrized by k. Previously we showed that contrary to Golomb s conjecture for each k there are many increasing solutions and an explicit construction for multiple solutions was displayed. By reformulating our solution approach using matrix dynamics we extend these results to a characterization of the asymptotic behaviour of all solutions of the Golomb recursion. This matrix dynamics perspective is also used to construct what we believe is the hrst example of a nontrivial nonincreasing solution that is one that is not eventually increasing. Subject Number 05A11 Key Words metahbonacci recursion Golomb recursion matrix dynamics 1 the electronic journal of combinatorics 4 1997 R16 2 1. Introduction In 3 Golomb introduced the recursion b b n kn 2b n kn 1 with initial conditions b 1 1 and b 2 3 for k 1 and b 2 2 for k 1. Here k is a fixed positive integer parameter and n ranges over the positive integers. This recursion which Golomb describes as strange was suggested to him by Fraenkel 2 who shows that one solution is given by b n _np_ where p is the positive root of the equation x2 k 2 x k 0 . 2 In the particular case that k 1 p is equal to T the golden ratio which satisfies T2 1 T and T 0. The sequence b n is called the homogeneous Beatty sequence of p. See 3 where a considerably more general recursion that 1 is discussed based upon iterates of the floor function _np for any algebraic number p. Golomb noted that the solution b n of 1 was not unique but conjectured that it appears to be the only monotonically increasing solution 4 p14 . In 1 Barbeau and Tanny showed that the recursion 1
