O William tem razão.
É possivel fazer uma indução mais simples
e limpa: basta "somar" os dois primeiros
caracteres e aplicar a hipótese de indução.
(Mas a hipótese de indução precisa ficar
mais complexa.)
Fórum