(Profmat-MA12 2011) Considere o conjunto dos números escritos apenas com os algarismos 1, 2 e 3, em que o algarismo 1 aparece uma quantidade par de vezes (por exemplo, 2322 e 12123). Seja a_{n} a quantidade desses números contendo exatamente n algarismos.
(a) Liste todos esses números para n=1 e n=2, indicando os valores de a_{1} e a_{2}.
(b) Explique por que a_{n} satisfaz a equação de recorrência
a_{n+1}=\left(3^{n}-a_{n}\right)+2 a_{n}, \text { para } n \geqslant 1 .

Passo 1

O enunciado pede para contar cadeias de comprimento n formadas pelos dígitos \{1,2,3\} em que o dígito 1 aparece um número par de vezes. Denotamos por a_n essa quantidade. Para resolver (a) listamos manualmente para n=1 e n=2. Para (b) usamos um argumento de extensão de cadeias pela paridade de ocorrências de 1.

Passo 2

Para n=1 as cadeias de um dígito são \;1,\;2,\;3.
Dessas, só valem as que têm número par de 1’s, ou seja, zero ocorrências de 1. Logo as válidas são \;2,\;3
e portanto
a_{1} = 2.

Passo 3

Para n=2 as cadeias possíveis são as 9 combinações de dois dígitos. Precisamos das que contêm 0 ou 2 ocorrências de 1.
  • Com 0 ocorrências de 1: dígitos em \{2,3\}\times\{2,3\}, ou seja \;22,\;23,\;32,\;33.
  • Com 2 ocorrências de 1: apenas \;11.
    No total são 5 cadeias, logo
a_{2} = 5.

Passo 4

Para deduzir a recorrência, considere todas as cadeias de comprimento n. Dessas, a_n têm número de 1’s par e 3^n - a_n têm número de 1’s ímpar. Ao estender cada cadeia em mais um dígito:
  1. Se o prefixo tem 1’s em par ( a_n casos), devemos não adicionar “1” (somente “2” ou “3”) para manter a paridade, gerando 2\,a_n cadeias.
  2. Se o prefixo tem 1’s em ímpar ( 3^n - a_n casos), só adicionar “1” corrige para par, gerando 3^n - a_n cadeias.
    Somando, obtemos
a_{n+1} = (3^{n} - a_{n}) \;+\; 2\,a_{n}.

Resposta

(a) a_{1}=2, a_{2}=5.
(b) Conforme o argumento de extensão,
a_{n+1}=(3^{n}-a_{n})+2\,a_{n}.

Exercícios relacionados