Let $A_n$ be the value of the greatest profundity of a $n$-letter in the dog dictionary. We'll prove by induction in $n$ that $A_n = F_{n + 3}-3$, and that the words $AUAU \dots $ and $UAUA \dots$ (both with $n$ letters) have profundity $A_n$. (Here, $F_n$ is the Fibonacci Sequence). To study the initial cases $n = 2,3$, we have to analyze the profundity of the words starting at $A$ (the study of words starting at $U$ is analogous, by symmetry) $n = 2$: $AA$ has profundity $1$ (sub-word $A$) and $AU$ has profundity $2=F_{5} - 3$ (sub-words $A$, $U$) $n = 3$: $AAA$ has profundity $2$ (sub-words $A$, $AA$); $AAU$ has profundity $4$ (sub-words $A$, $U$, $AA$, $AU$); $AUA$ has profundity $5=F_{6}-3$ (sub-words $A$, $U$, $AU$, $UA$, $AA$); $AUU$ has profundity $4$ (sub-words $A$, $U$, $AU$, $UU$). In order to do the inductive step $n \ge 4$, we will need two statements: Statement 1: $AUAU \dots$ ($n$ letters) has exactly $F_{n + 3} -3$ sub-words, as well as $UAUA \dots $ ($n$ letters) Proof: Every sub-word of $AUAU ...$ ($n$ letters) that begins with $A$ is either $A$ or is of the form $AX$, where $X$ is a sub-word of $UAUAU \dots$ ($n-1$ letters) and as there is $A_{n-1}$ possibilities for $X$ (by hypothesis), we have $1 + A_{n-1}$ sub-words of this type. Every sub-word of $AUAU \dots$ ($n$ letters) that begins with $U$ is either $U$, or is $UAUA \dots$ ($n-1$ letters), or is of the form $UY$, where $Y$ is a sub-word of $AUAU \dots$ ($n-2$ letters) . Since there are $A_{n-2}$ possibilities for $Y$ (by hypothesis), we have $2 + A_{n-2}$ sub-words of this type. Thus, the number of sub-words of $AUAU \dots$ ($n$ letters) is $(1 + A_{n-1}) + (2 + A_{n-2}) = 3 + A_{n-1} + A_{n-2}$, which, by hypothesis, is $3+(F_{n + 2} -3) + (F_{n + 1} -3) = F_{n + 3} -3$, as we wanted to prove. The $UAUA \dots$ ($n$ letters) study is analogous. Statement 2: $A_n \le 3 + A_{n-1} + A_{n-2}$, for all $n \ge 4$. Proof: Let $T = X_1 X_2 \dots X_n$ be a $n$-letter word with profundity $A_n$, where $X_i \in {A, U}$, and suppose WLOG $X_1 = A$. If all $X_i = A$, then $A_{n}=n-1< F_{n+3} - 3$, which is absurd by Statement 1, since $A_n$ is maximum. So, there is $c \in \{ 2, \dots , n \}$ such that $X_c = U$ and $c$ is minimal. Now, observe that every sub-word of $T$ beginning with $A$ is either $A=X_1$ or $AX$, where $X$ is a sub-word of $X_2 \dots X_n$ and as there is at most $A_{n-1}$ possibilities for $X$ (by hypothesis), we have at most $1 + A_{n-1}$ sub-words of this type. Every sub-word of $T$ beginning with $U$ is either $U=X_c$, or is $X_c \dots X_n$, or is of the form $X_c Y$, where $Y$ is a sub-word of $X_{c+1} \dots X_n$ . Since there are at most $A_{n-c}$ possibilities for $Y$ (by hypothesis), we have at most $2 + A_{n-c}$ sub-words of this type. Therefore, $A_n \le (1+A_{n-1}) + (2+ A_{n-c}) = 3 + A_{n-1} + A_{n-c} \le 3+ A_{n-1} + A_{n-2}$, since $(A_n)$ is clearly non decreasing. Finally, by hypothesis and Statement 2, $A_n \le 3 +(F_{n + 2} -3) + (F_{n + 1} -3) = F_{n + 3} -3$ and because we have example with profundity $F_{n + 3} -3$, the result follows by induction.