Q3 Matemática  (Rioplatense Mathematical Olympiad, Level 3 2019)

No dicionário para cães, as palavras são qualquer sequência de letras $A$ e $U$, por exemplo, $AA$, $UAU$ e $AUAU$. Para cada palavra, sua "profundidade" será a quantidade de subpalavras que podemos obter pela retirada de algumas letras. Para cada inteiro positivo $n$, determine a maior "profundidade" que a palavra, no dicionário canino, pode ter com $n$ letras. Nota: A palavra $AAUUA$ tem "profundidade" $14$ porque suas subpalavras são $A,U,AU,AA,UU,UA,AUU,UUA,AAU,AUA,AAA,AAUU,AAUA,AUUA$.