Given characters $\{a, b\}$ where some string must begin with $a$ and end with $b$, how do I show that the sequence $ab$ will appear in the string? We have a string that consists of characters in the set $\{a,b\}$ that begins with the character $a$ and ends with the character $b$.
Prove using the method of Strong Induction that the sequence $ab$ will appear in the string.
Here is my best attempt to prove this:
Theorem. Given a string that consists of characters in the set $\{a, b\}$, that begins with the character $a$ and ends with the character $b$, the sequence $ab$ will appear in the string.
Proof. The proof is by strong induction. Let $S(n)$ be some string of length $n$ where $n \in \mathbb{N}$, $n \ge 2$, such that the string consists of characters in the set $\{a, b\}$ that begins with the character $a$ and ends with the character $b$.
Base case: If $n = 2$, then our string is of length $2$ and is thus the trivial case of the string $ab$. So, $S(2)$ is true. 
Inductive Step $\forall k \in \mathbb{N}$, where $k \ge 2$, we assume that $S(2), ..., S(k)$ are all true and we now show that $S(k + 1)$ is true, namely that a string of length $k + 1$ also contains the sequence $ab$.
Given a string of length $k + 1$, for $k \ge 2$, we observe the previous character and note that we can have $2$ possible cases:


*

*If the $k$th character is $a$, then we know the string contains the sequence $ab$ since we are given that the $k + 1$ will be $b$. 

*If the $k$th character is $b$, then the previous character, $k - 1$, must be either $a$ or $b$. 
If the $k-1$ character is $a$, then we have found an $ab$ sequence in the string. 
If the previous character, $k-1$ is a $b$, then we know that we either have the character $a$ in the $k - 2$ position of the string or we have the character $b$ in the $k - 2$ position of the string. 
If there exists a character $a$ in some position $m$ in the string, for $2 \le m \le k-2$, then we have found an $ab$ sequence in the string. If all the characters from position $2$ up to and including position $k-2$ are $b$ then, we are still guaranteed to have the sequence $ab$ in our string since we are given that the first character of the string must be $a$.   
Thus, $S(k + 1)$ is true.
Therefore, it follows by induction that the theorem is true $\forall n \in \mathbb{N}$, $n \ge 2$
 A: Use a simple induction on the size of the string n (>=2).
Base case "ab" is trivial. (n=2)
For case of length k+1 (where k>=2), look at the kth character. If this is an 'a', we are done as the last letter( (k+1)th ) is a 'b'. Else, use induction on the prefix of length k.
A: The revised proof is much better than the first attempt. The induction step is set up in a way that is really appropriate for the way the string was described. And case $1$ looks pretty airtight.
The revised proof still seems to grope around a bit in case $2.$ The claims in the argument are obviously true; compare the proof in the answer by Lars Helenius. So this part of the proof has the right idea underneath it, I think, although it seems not quite as "inductive" as one might want.

Note: The following remarks apply to the earlier version of the proof;
these issues have been resolved in the updated question.
It was not clear at all to me that the proof originally presented in the question (inserting a character into a string of length $k$ to make a
string of length $k+1$) was valid.
It assumes that every string in the set (except $ab$) can be generated by inserting one letter into another string in the set.
I think that statement will turn out to be true, but that doesn't mean
you can just take it as given without proof.
If the set were defined inductively, by stating that the set contained
the string $ab$ and all other strings were obtained by performing the operations in your four cases one or more times on that string,
then the proof would be valid.
But the set was not defined that way.
A: Suppose the string in question doesn't contain $ab$. Then $a$ (the initial character of the string) can never transition to $b$ as we scan the word from left to right. This means the string would end in $a$, a contradiction (in fact, it would be a string of all $a$'s).
