Problema
(Indicado a partir do 1º ano do E. M.)
A sequência [tex](0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, \dots)[/tex] é conhecida como sequência de Thue-Morse em homenagem aos matemáticos Axel Thue (1863-1942) e Marston Morse (1892-1977). Denotando por [tex]a_n[/tex] o valor do termo da posição [tex]n[/tex], essa sequência pode ser definida pelas fórmulas de recorrências
[tex]\qquad{a_1=0;}[/tex]
[tex]\qquad{a_{2n+1}=a_{n+1};}[/tex]
[tex]\qquad{a_{2n}=1-a_n}.[/tex]
Calcule o valor de [tex]a_{1200}[/tex].
Solução
Usando a parte da fórmula de recorrência para posições pares, obtemos:
[tex]\qquad{a_{1200}=1-a_{600}=1-(1-a_{300})=a_{300}=1-a_{150}=1-(1-a_{75})=a_{75}}.[/tex]
Usando as duas partes da fórmula de recorrência, obtemos:
[tex]\qquad{a_{75}=a_{2\times37+1}=a_{38}=1-a_{19}=1-a_{2\times 9+1}=1-a_{10}.}[/tex]
Os valores iniciais da sequência fornecem [tex]a_{10}=0[/tex]. Portanto, [tex]a_{1200}=1-a_{10}=1-0=1.[/tex]
Solução elaborada pelos Moderadores do Blog.