Considere o conjunto das sequências de tamanho tais que cada entrada pertence a e entradas vizinhas sempre diferem por 1 em módulo. Descreva um sistema de equações de recorrência para resolver este problema.
Passo 1
Beleza, vamos dar uma olhada nesse exercício! A gente precisa trabalhar com sequências de tamanho onde cada número na sequência pode ser 0, 1, 2 ou 3. Além disso, números que estão um ao lado do outro na sequência têm que diferir exatamente por 1, considerando o módulo (ou seja, diferenças circulares). Nosso objetivo aqui é montar um sistema de equações de recorrência que nos ajude a contar quantas dessas sequências são possíveis para um determinado .
Passo 2
Primeiro, vamos entender melhor o que são equações de recorrência. Elas são como receitas que nos permitem calcular termos em uma sequência usando os termos anteriores. No nosso caso, queremos expressar o número de sequências de tamanho em função do número de sequências de tamanhos menores.
Passo 3
Vamos chamar de o número de sequências de tamanho que terminam em 0, 1, 2 e 3, respectivamente. Isso ajuda a organizar nossa contagem com base no último número da sequência.
Passo 4
Agora, vamos pensar nas possíveis maneiras de chegar a um número final específico, considerando que números vizinhos precisam diferir por 1 (mod 4).
Terminar com 0 (): O número anterior tem que ser , porque e diferem por 1.
Terminar com 1 (): O número anterior pode ser ou , já que ambos diferem de por 1.
Terminar com 2 (): O número anterior pode ser ou .
Terminar com 3 (): O número anterior tem que ser , porque e diferem por 1.
Passo 5
Com base nisso, podemos escrever as seguintes equações de recorrência:
Aqui, cada equação expressa o fato de que para uma sequência terminar com um certo número, o número anterior tem que ser um dos permitidos conforme discutimos.
Passo 6
Essas equações formam um sistema de recorrência que podemos usar para calcular o número de sequências para qualquer tamanho , começando com condições iniciais apropriadas (como para ).