# Fibonacci Numbers: Is This Notation Clear? How Can It Be Improved?

I am writing up an assignment with includes many identities of Fibonacci numbers. I have made up the following notation (here $f_n$ is the number of tilings of an $n$-board by dominoes and squares - a well known interpretation of Fibonacci numbers):

Given an $n$-board, and some sequence $seq$ of dominos and squares, let $f_n^{seq}$ represent all tilings of an $n$-board that end with the sequence $seq$. So for example $f_n^{DS}$ are all tilings of an $n$-board that end with a domino succeeded by a square. Furthermore, for repeating sequences write: $$\underbrace{seq,seq, \cdots, seq}_{n-\text{times}} = n\cdot seq$$ So for example $f_n^{SSDSDSDSDS} = f_n^{2S4DS}$. Let the size of a sequence $|seq|$ be the number of tiles the sequence occupies, so $|SS4DS| = 14$. It is clear that: $$f_n^{seq} = f_{n - |seq|}$$

How may this be improved? Are statements such as

$$f_{3n-3k} = f_{3n}^{kDS} = f_{3n}^{SSkDS} + f_{3n}^{DkDS} + f_{3n}^{(k+1)DS} = f_{3n-3k}^{SS} + f_{3n-3k}^{D} + f_{3n-3k}^{DS} =$$ $$= 2f_{3n-3k-2} + f_{3n-3k-3}$$

a bit understandable without explanation? (I do offer an explanation of course).

-
What's an n-board? – Dan Moore Mar 1 '11 at 14:49
An $1\times n$ board to be precise :) – milcak Mar 1 '11 at 16:32

Putting all that into a superscript (especially with the exponential notation suggested by others) is hard on the eyes. How about:

$f_{3n-3k} = f_{3n}(*(DS)^k) = f_{3n}(*SS(DS)^k) + f_{3n}(*D(DS)^k) + f_{3n}(*(DS)^{k+1})$

etc. Here * represents any sequence (so the argument in parentheses is not the end of the sequence, it's the whole sequence).

-
Agreed. I would even write the left-hand side as $f_{3n-3k}(*)$. – Greg Graviton Mar 1 '11 at 16:15

I must say that I don't find your $n \cdot seq$ easy to read, and it can appear ambiguous. I'd be inclined to borrow from automata theory and write e.g. $SSDSDSDSDS$ as $S^2(DS)^4$.

I would be inclined to help the lazy reader by also reminding him with the notation that you're talking about the end of sequences, so $\ldots S^2(DS)^4$.

I'm not sure how aesthetic this is when superscripted, but you can see for yourself: $f_{3n}^{\ldots S^2(DS)^4}$

-
Yes that is a bit better. I definitely agree on the $\cdots$, but since usually in the proof I use only at most one repeating sequence, I think $(kDS)$ is ok, otherwise it would get more confusing. Thanks! – milcak Mar 1 '11 at 11:19
@Milcak: You still get ambiguity when writing $(3DS)$. Does that mean $DDDS$ or $DSDSDS$? – t.b. Mar 1 '11 at 11:23

Since the topic relates to ordered partitions of n, I would try to dovetail with existing nomenclature for ordered partitions. In particular, I suggest using 2 instead of D and 1 instead of S.

-
This would not be as clear for combinatorial proofs. Dominoes and squares are magic. $1$'s and $2$'s are not (so much). :) – milcak Mar 1 '11 at 17:29