Como se desarrolla este ejercicio de sucesiones recurrentes?

Toda cadena de estacionamiento es una palabra formada por las letras a y m

Para n=1 {m}

Para n=2 {mm, a}

Para n=3 {mmm, am, ma}

Para n=4 {mmmm, amm, mam, mma, aa}

Para n=5 {mmmmm, ammm, mamm, mmam, aam, mmma, ama, maa}

Dado un número n >2 las palabras acabarán en m o a. Si quitamos la m final tendremos las palabras de n-1 y si quitamos la a tendremos las palabras de n-2. Luego

Palabras(n) <= Palabras(n-1) + Palabras(n-2)

A cualquier palabra de n-1 a la que añadamos la letra m al final nos dará una palabra de n distinta, y a cada palabra de n-2 a la que añadamos la letra a nos dará una palabra de n distinta, además las que hemos añadido m serán distintas de las que hemos añadido a, luego

Palabras(n-1) + Palabras(n-2) <= Palabras(n)

Y de las dos desigualdades se deduce:

Palabras(n) = Palabras(n-1)+Palabras(n-2)

Si te fijas esa es la estrategia que seguí para escribir las formas, tomaba las de n-1 y les añadía la m, luego tomaba las de n-2 y les añadía la a

En lenguaje más propio de sucesiones sería:

$$\begin{align}&a_1=1\\&a_2=2\\&a_n=a_{n-1}+a_{n-2}\end{align}$$

Es la sucesión de Fibonacci: 1, 2, 3, 5, 8, 13, 21, 34, 55, ...