Fibonacci String Ends with ab or ba

Theorem

Let $S_n$ be a Fibonacci string of length $n$.

Then for $n \ge 3$, $S_n$ ends either with $\text{ba}$ or with $\text{ab}$.

Proof

The proof proceeds by induction.

For all $n \in \Z_{\ge 3}$, let $P \left({n}\right)$ be the proposition:

$S_n$ ends either with $\text{ba}$ or with $\text{ab}$

We note in passing that $S_1 = \text a$ and $S_2 = \text b$, so neither of these ends either with $\text{ba}$ or with $\text{ab}$.

Basis for the Induction

$P \left({3}\right)$ is the case:

$S_3 = \text{ba}$

Thus $P \left({3}\right)$ is seen to hold.

$P \left({4}\right)$ is the case:

$S_4 = \text{bab}$

Thus $P \left({4}\right)$ is seen to hold.

This is the basis for the induction.

Induction Hypothesis

Now it needs to be shown that, if $P \left({k}\right)$ is true, where $k \ge 3$, then it logically follows that $P \left({k + 1}\right)$ is true.

So this is the induction hypothesis:

$S_k$ ends either with $\text{ba}$ or with $\text{ab}$

and:

$S_{k - 1}$ ends either with $\text{ba}$ or with $\text{ab}$

from which it is to be shown that:

$S_{k + 1}$ ends either with $\text{ba}$ or with $\text{ab}$

Induction Step

This is the induction step:

By definition of Fibonacci string:

$S_{k + 1} = S_k S_{k - 1}$

concatenated.

So $S_{k + 1}$ end with $S_{k - 1}$.

By the induction hypothesis, $S_k$ ends either with $\text{ba}$ or with $\text{ab}$.

Thus $S_{k + 1}$ likewise ends either with $\text{ba}$ or with $\text{ab}$.

So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore:

for all $n \in \Z$ such that $n \ge 3$, $S_n$ends either with $\text{ba}$ or with $\text{ab}$.