6. Are They All Even?

Problem set by Clark Kimberling.

Solution by Michael Behrend: the answer is yes.

Note: Clark Kimberling labels the rows 1, 2, 3, …. For this solution it is more convenient to label the rows 0, 1, 2, …, and I have made this change when copying the following statement of the problem. Also, I use Φ for (1 + sqrt(5))/2. – MB.

Begin an array [row 0] by writing the Fibonacci numbers: 1, 2, 3, 5, 8, ... Start row 1 with the least unused positive integer, which is 4; follow 4 by 6, and finish the row using the Fibonacci recurrence (i.e., add the two most recent numbers to produce the next, so that row 1 starts with 4, 6, 10, 16, 26, 42). Start row 2 with the least unused, which is 7, follow 7 by 12, and then use the recurrence to produce 19, 31,.... Continue in this manner (the choice of second term in each new row is revealed below), getting rows 0 to 3 starting like this:

1    2    3    5     8    13 . . .

4    6   10   16   26   42 . . .

7   12   19   31   50   81 . . .

9   14   23   37   60   97 . . . .
.
.

Here is the recipe for the second number in each row: let Φ be the golden ratio, (1+sqrt(5))/2, let i be the number of the row [i = 0 for top row], and let x be the first number in the row; then the second number is [Φx] if i is odd, and it is [Φx] + 1 if i is even.

For example, row 4 starts with the least unused, which is x=11, and this is followed by [11Φ] + 1, which is 18.

Is every number is column 2 even?

In anticipation that the answer is yes, the array is introduced as the Even Second Column Array in

C. Kimberling, "The First Column of an Interspersion," The Fibonacci Quarterly 32 (1994) 301-315.


The solution, plus some alternative proofs of known results, is now published in The Fibonnaci Quarterly, 50(2) (May 2012), 106–118. The full paper is available on the FQ website. NB: Access to recent issues of the FQ is by subscription only.

A version containing the solution only in PDF format is available on this website.