For Exercises 49–51, we define inflation and deflation of a sequence of “tiles” consisting of s (“shorts”) and s (“longs”).
- Inflation: Replace each by and each by . For example, the inflation of ()()() would be , where we have inserted parentheses for clarity.
- Deflation: Replace each by and each lone by . For example, the deflation of ()()() would be , where we have inserted parentheses for clarity.
Question 20.81
51. Let a lone be considered the first stage of inflation. Show that at the nth stage of inflation, for , there are (the th Fibonacci number—see Section 19.1 on page 780) symbols in the sequence, of which are s and are s. (Hint: Check it for , and 4.)
51.
Let and be the number of Ls and the number of s at the th stage. Each at the th stage (for ) must have come from one in the previous stage, so . Similarly, we get an at the th stage from each and each in the previous stage, so . Using both these facts together, we have . We note that ,
. The sequence obeys the same recurrence rule as the Fibonacci sequence and starts with the same values one step later; in fact, it is always just one step behind the Fibonacci sequence: . Consequently, , and the total number of symbols is .