# »  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φ