»  Solutions to puzzles in my National Review Online Diary

  May 2011

—————————

In my May diary I posed the following brain-teaser.

Define strings S1, S2, S3, … as follows:
S1 = the string consisting just of "a"

S2 = the string consisting just of "b"

Sk = the string you get by concatenating Sk−1 with Sk−2
If you just apply that definition you get a sequence of strings like this:
S3 = "ba"

S4 = "bab"

S5 = "babba"

S6 = "babbabab"

S7 = "babbababbabba"

S8 = "babbababbabbababbabab"

  … … …

Sn = "babbababbabbababbababbabbababbabba …"
Since, by definition, every string Sn begins with the string Sn−1, it's possible to imagine the string S, which the author of the AMM article calls "the golden string."

Your mission, should you decide to accept it, is to find an expression for the position in S at which the n-th "b" occurs. The answer is of course some function of n, but what function?

—————————

Solution

An observation, then some exploration.

Observation:  The Fibonacci sequence is obviously going to figure in here somewhere. The length of the string Sn is Fn, by the rule of construction. (If, like me, you have trouble remembering how the Fibonacci sequence is indexed, the key is that F5 = 5. Here just for reference, are the Fibonacci numbers Fn for n = 1 to 20:   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765.)

Exploration:  Let's look at some actual values of the function we seek, for n = 1 to 100. When n is a Fibonacci number, I've noted the fact, just to see if it illuminates anything.

n     Position of    
the n-th
"a"
    Position of    
the n-th
"b"
  F2 = 1   2   1  
  F3 = 2   5   3  
  F4 = 3   7   4  
4   10   6  
  F5 = 5   13   8  
6   15   9  
7   18   11  
  F6 = 8   20   12  
9   22   14  
10   25   16  
11   27   17  
12   30   19  
  F7 = 13   34   21  
14   36   22  
15   39   24  
16   41   25  
17   44   27  
18   47   29  
19   49   30  
20   52   32  
  F8 = 21   54   33  
22   57   35  
23   60   37  
24   62   38  
25   65   40  
26   68   42  
27   70   43  
28   73   45  
29   75   46  
30   78   48  
31   81   50  
32   83   51  
33   86   53  
  F9 = 34   89   55  
35   91   56  
36   94   58  
37   96   59  
38   99   61  
39   102   63  
40   104   64  
41   107   66  
42   109   67  
43   112   69  
44   115   71  
45   117   72  
46   120   74  
47   123   76  
48   125   77  
49   128   79  
50   130   80  
51   133   82  
52   136   84  
53   138   85  
54   141   87  
  F9 = 55   143   88  
56   146   90  
57   149   92  
58   151   93  
59   154   95  
60   157   97  
61   159   98  
62   162   100  
63   164   101  
64   167   103  
65   170   105  
66   172   106  
67   175   108  
68   178   110  
69   180   111  
70   183   113  
71   185   114  
72   188   116  
73   191   118  
74   193   119  
75   196   121  
76   198   122  
77   201   124  
78   204   126  
79   206   127  
80   209   129  
81   212   131  
82   214   132  
83   217   134  
84   219   135  
85   222   137  
86   225   139  
87   227   140  
88   230   142  
  F9 = 89   233   144  
90   235   145  
91   238   147  
92   240   148  
93   243   150  
94   246   152  
95   248   153  
96   251   155  
97   253   156  
98   256   158  
99   259   160  
100   261   161  

We sure do have some illumination. It looks as though the Fk -th "b" will be found at position Fk+1 when k is odd, and at position Fk+1 − 1 when k is even. (With a similar rule for the a's … but I'm going to ignore them from here on.)

What does this suggest? Let's bring in the golden ratio 1.6180339887498948482045868343 …, nowadays usually denoted by φ (the Greek letter phi).

This number φ is intimately connected with the Fibonacci sequence. For example: if you divide a Fibonacci number by the previous one, you get φ, plus or minus a small error that dwindles fast as you go along the sequence. So 13/8, for example, is 1.625, which differs from φ by less than half of one percent. A bit further along the sequence, 6765 divided by 4181 gives 1.6180339631667065295383879454 …, which differs from φ by less than one part in fifty million.

So those entries in the table for which n is a Fibonacci number show the position of the n-th "b" as being the next Fibonacci number, i.e. approximately φn. There's a good first guess as to the answer: The n-th "b" is at position φn. That can't be exactly right, of course, since φn is never a whole number (because φ is irrational), but from a quick exploration, it's not bad.

—————————

OK, let's get formal.

Our exploration turned up a very suggestive result for the position of the n-th "b" when n is a Fibonacci number. Alas, not every positive whole number is a Fibonacci number. It's not the position of the Fk -th "b" that we want, it's the position of the n-th "b" in general.

However, even though not every n is an Fk, Fibonacci theory offers us something almost as good: Zeckendorf's Theorem, which says that every positive whole number n is the sum of different non-consecutive Fibonacci numbers, F1 excluded. (Since F1 = F2, including F1 would foul up the "different" condition.)

(Zeckendorf's Theorem actually says slightly more than that, but that's all we need.)

More formally:

For any positive whole number n it is the case that n = Fp + Fq + Fr + …, where p, q, r, … are all different, no two are consecutive, and none is equal to 1.

(I'm actually going to assume here and from now on that p, q, r, … are in descending order. So for example 100 = F11 + F6 + F4.)

That's one of the key facts we need — call it Fact I.

Here's another, Fact II. Suppose we have — as by the above-mentioned theorem we always can have — a decomposition of n into Fp + Fq + Fr + …, the p, q, r, … descending in size. Then by concatenating the strings Sp, Sq, Sr, …, in that order, I will get the first n positions of the golden string S.

I shan't pause to prove Fact II. You can do a formal proof by induction, but it follows quite easily from the rules for constructing the strings.

So for example, 12 = 8 + 3 + 1, so 12 = F6 + F4 + F2. Therefore the first 12 positions of the golden string are the concatenation of S6, S4, and S2. If you concatenate those strings as I listed them above, in that order, and compare with the first 12 positions of S, you will see that this is correct.

Here's yet another fact, Fact III. Recall the the length of the string Sk is Fk. How many of those Fk positions contain a "b"? The answer is Fk−1. You can check this out with the strings I started with, and it follows fairly immediately from the rules for constructing the strings.

Now for the last and biggest of my facts, Fact IV. The actual precise relation between the Fibonacci numbers and the golden ratio φ is this:

Fk  =  (φk − (−φ)k) / √5

There's a proof of that in my book Unknown Quantity, Endnote 35. It's a fundamental fact of Fibonacci theory though, and you should have no difficulty finding a proof on the net, if you're too damn cheap to buy my book.

Just writing k−1 in place of k gives this:

Fk-1  =  (φk−1 − (−φ)−(k−1)) / √5

Those two results combined, after a bit of algebraic manipulation, give this:

Fk /φ =  Fk−1  + (−1)k−1[φ−(k−1) + φ−(k+1)] / √5

I'm going to call that Fact IVa. It's the main key to the proof.

Go back to my number n. How many b's are there in the first n letters of S?

Well, decompose n by Zeckendorf's Theorem into Fp + Fq + Fr + …. By Fact II and Fact III, the number of b's in those first n positions of S will be Fp−1 + Fq−1 + Fr−1 + ….

Now just add up all the statements of Fact IVa with k replaced in turn by p, q, r, …. The Fk's add up to n and the Fk−1's add up to the number of b's in the first n positions of S!

The number of b's in the first n positions of S is not precisely what I'm looking for, but it sure seems like it would help. I'll call it Cb(n), read as "count of b's in the first n positions." Then adding up all those Fact IVa's got me this:

n/φ = Cb(n) + ∑{(−1)k−1[φ−(k−1) + φ−(k+1)]} / √5

 … where the sum is taken over k = p, q, r, …

That sum looks a bit gruesome, but if you separate out the even and odd powers of −1, you just get two sums:  the first, with a minus sign in front, of a bunch of (φs +φt), where s and t are consecutive odd numbers, and the second, with a plus sign in front, of a bunch of (φu +φv), where u and v are consecutive even numbers.

Those are both finite sums; but since all the terms are positive, each is less than the corresponding infinite sum. I can work out the infinite sums using the rule  1 + x + x2 + x3 + x4 + … = 1 / (1 − x)  together with the basic φ identities (φ2 = φ + 1 helps a lot). I get answers −√5 / φ for the odd terms and √5 / φ2 for the even.

So, since we've added up infinite series of which only some finite part is actually in play, it is certainly the case, substituting the lowest and highest possible results for the joint sum, that:

n/φ > Cb(n) − 1/φ

While also:

n/φ < Cb(n) + 1/φ2

That implies:

Cb(n) < (n + 1) / φ < Cb(n) + 1

A neater way to express that mathematically is:

Cb(n) = ⌊(n + 1) / φ

Those partial brackets represent the floor function: ⌊x⌋ is the biggest whole number not bigger than x. For example, ⌊π⌋ = 3, and so is ⌊3⌋ = 3 (since 3 is not bigger than 3). However, ⌊−π⌋ = −4. (The floor function is actually called Floor in Mathematica, though it's Int in Visual Basic.)

That's not the final result, but the final result follows very easily, and I want my dinner.

Solution:   The n-th "b" of S occurs at position ⌊nφ