Sala de Estudo: Recorrências – Sala 2

Denotaremos por [tex]a_{10}[/tex] a solução do problema, ou seja, o número de maneiras possíveis para a colocação de dez lâmpadas enfileiradas, de modo que não haja lâmpadas adjacentes acesas.

• Para iniciarmos a discussão, observamos duas situações possíveis e complementares ao enfileirarmos as lâmpadas:

Caso 1: A primeira lâmpada está acesa; Caso 2: A primeira lâmpada está apagada.

Dessa forma, temos que:

[tex]\boxed{a_{10}= \text{soluções com a primeira lâmpada acesa + soluções com a primeira lâmpada apagada.}}[/tex]

• Pela restrição imposta no enunciado, note que se a primeira lâmpada estiver acesa, obrigatoriamente a segunda deve ficar apagada.



Assim, passamos para um “novo” problema com as mesmas restrições do problema inicial, porém teremos [tex]8[/tex] lâmpadas. Chamaremos de [tex]a_8[/tex] a solução do problema para [tex]8[/tex] lâmpadas.

• De forma análoga, se a primeira lâmpada estiver apagada, a segunda pode estar acesa ou não.



Assim, também chegamos a um “novo” problema com as mesmas restrições do problema inicial, porém com [tex]9[/tex] lâmpadas. De forma análoga, chamaremos de [tex]a_9[/tex] a solução do problema para [tex]9[/tex] lâmpadas.

Essa estratégia de reduzir o problema em casos menores nos mostrou que:

[tex]\boxed{a_{10}=a_9+a_8}[/tex],

ou seja, a solução do problema para [tex]10[/tex] lâmpadas é a soma das soluções para [tex]9[/tex] lâmpadas com as soluções para [tex]8[/tex] lâmpadas.
Seguindo esse mesmo raciocínio, podemos generalizar essa relação para uma bancada com [tex]n[/tex] lâmpadas:

[tex]\boxed{a_{n}=a_{n-1}+a_{n-2}}. \qquad \qquad \textcolor{#3f695f}{(i)}[/tex]

A relação [tex]\textcolor{#3f695f}{(i)}[/tex] nos mostra que o número de soluções para uma bancada com [tex]n[/tex] lâmpadas é a soma do número de soluções para [tex]n-1[/tex] lâmpadas com o número de soluções para [tex]n-2[/tex] lâmpadas.
A fórmula [tex]\textcolor{#3f695f}{(i)}[/tex] é o que chamamos na Matemática de lei de formação de uma sequência e, nesse caso, ela foi dada recursivamente. Por isso, ela é dita uma fórmula de recorrência. Para que essa fórmula seja realmente eficaz, devemos conhecer pelo menos dois termos consecutivos da sequência. Por facilidade, vamos calcular os dois termos iniciais.

• Imaginemos o problema inicial com apenas uma lâmpada na bancada. Seguindo todas as restrições do enunciado, teremos duas soluções (ou a lâmpada estará acesa ou estará apagada); portanto, [tex]a_{1}=2[/tex].
• Se a bancada tivesse duas lâmpadas, teríamos [tex]3[/tex] soluções:

• Ambas apagadas;



• A primeira acesa e a segunda apagada;



• A primeira apagada e a segunda acesa.



Logo, [tex]a_{2}=3.[/tex]

Para efeito de ilustração, vamos observar dois casos particulares da fórmula que deduzimos.

(1) Segundo nossa relação, o número de soluções do problema para uma bancada com [tex]3[/tex] lâmpadas seria a soma das soluções para o problema com uma única lâmpada com as soluções para uma bancada com duas lâmpadas, ou seja, [tex]a_{3}=2+3=5[/tex]. Vamos verificar?
Se a bancada estivesse com [tex]3[/tex] lâmpadas, temos três casos a considerar:
• Nenhuma lâmpada acesa;



• Apenas uma lâmpada acesa;



• Duas lâmpadas acesas;



totalizando as esperadas [tex]5[/tex] soluções.

(2) Podemos visualizar as soluções para uma bancada com [tex]4[/tex] lâmpadas clicando AQUI.

[tex]\, \, [/tex]
Finalmente, podemos escrever a fórmula de recorrência completa e a sequência que nos permite responder a pergunta do problema:

[tex]\boxed{\begin{cases} a_{n}=a_{n-1}+a_{n-2},\, \, n\ge 3 \\ a_{1}=2 \\a_{2}=3 \end{cases}}[/tex]
[tex]a_{1}=2[/tex]
[tex]a_{2}=3[/tex]
[tex]a_{3}=5[/tex]
[tex]a_{4}=8[/tex]
[tex]a_{5}=13[/tex]
[tex]a_{6}=21[/tex]
[tex]a_{7}=34[/tex]
[tex]a_{8}=55[/tex]
[tex]a_{9}=89[/tex]
[tex]a_{10}=144[/tex]

Portanto, para uma bancada com dez lâmpadas, teremos [tex]\, \fcolorbox{#589386}{#ddebe8}{$144$}[/tex] maneiras de enfileirarmos as lâmpadas, de acordo com as restrições do problema.

• Inicialmente, vejamos a sequência de movimentos para a resolução do problema com [tex]3[/tex] discos.
• Posição inicial



• Primeiro movimento



• Segundo movimento



• Terceiro movimento



• Quarto movimento



• Quinto movimento



• Sexto movimento



• Sétimo movimento



[tex]\, [/tex]
Assim, resolvemos o jogo com [tex]3[/tex] discos fazendo [tex]7[/tex] movimentos.

Agora, vamos encontrar uma relação para o número mínimo de movimentos em um jogo com [tex]4[/tex] discos e depois generalizar o raciocínio para com [tex]n[/tex] discos. Usaremos a notação do Exemplo anterior, na qual os índices representarão a quantidade de discos e o valor do termo a quantidade de movimentos. Pelo que acabamos de resolver, [tex]a_{3}=7[/tex].

• Para resolver o jogo com [tex]4[/tex] discos, note que vamos passar por [tex]3[/tex] etapas:
• Etapa 1: Deslocar os [tex]3[/tex] discos menores para outra Torre;



• Etapa 2: Mover o disco maior;



• Etapa 3: Mover os [tex]3[/tex] discos menores para a Torre onde está o disco maior;



Portanto, para resolver o jogo com [tex]4[/tex] discos, primeiro resolvemos o jogo com [tex]3[/tex] discos, realizamos mais um movimento e depois resolvemos, novamente, o problema para [tex]3[/tex] discos. Assim, [tex]a_{4}=a_{3}+1+a_{3}[/tex], ou seja, [tex]a_{4}=2a_{3}+1[/tex].

Podemos usar essa ideia para generalizar quando a Torre inicial tiver [tex]n[/tex] discos:

• Deslocamos os [tex]n-1[/tex] discos menores para uma segunda haste, segundo as regras;
• Movemos o disco maior;
• Movemos, segundo as regras, os [tex]n-1[/tex] discos menores para a haste onde está o disco maior.

Com isso, segue que:
[tex]\qquad \qquad a_{n}=a_{n-1}+1+a_{n-1}[/tex]
[tex]\qquad \qquad a_{n}=2a_{n-1}+1.[/tex]

Acabamos de encontrar uma fórmula de recorrência para o jogo da Torre de Hanói. Tal fórmula ficará bem definida quando fixarmos as condições iniciais. Por facilidade, usaremos como primeiro termo da sequência a solução do jogo com apenas um disco. Não é difícil perceber que [tex]a_{1}=1[/tex].
Assim:

[tex]\begin{cases} a_{n} =2a_{n-1}+1,\, \, n \ge 2 \\ a_{1} = 1 \end{cases}[/tex]

Podemos, então, calcular os termos iniciais da sequência com os números mínimos de movimentos e responder qual o número mínimo para resolver o jogo com [tex]6[/tex] discos:

[tex]a_{1}=1[/tex];
[tex]a_{2}=3[/tex];
[tex]a_{3}=7[/tex];
[tex]a_{4}=15[/tex];
[tex]a_{5}=31[/tex];
[tex]a_{6}=63[/tex].

Portanto, [tex]\, \fcolorbox{#589386}{#ddebe8}{$63$}[/tex] é o número mínimo de movimentos necessários para resolvermos o jogo da Torre de Hanói com seis discos.

Vamos chamar de [tex]d_{n}[/tex] o número de diagonais do polígono convexo de [tex]n[/tex] lados. No enunciado do problema, foi informado que [tex]d_{24}=x[/tex] e pedido, em função de [tex]x[/tex], o valor de [tex]d_{25}[/tex]. Analogamente ao que fizemos nos problemas anteriores, vamos começar estudando casos mais simples para em seguida generalizar.

• Imaginemos um polígono de [tex]6[/tex] lados (hexágono) e chamemos dois de seus vértices de [tex]A[/tex] e [tex]B[/tex]. O número de diagonais desse polígono é [tex]d_{6}[/tex].



• Agora, vamos construir mais um vértice [tex](C)[/tex] para esse polígono, entre os vértices [tex]A[/tex] e [tex]B[/tex]. Assim, obtemos um polígono de [tex]7[/tex] lados (heptágono).



Inicialmente, note que as diagonais do polígono de [tex]6[/tex] lados também são diagonais desse novo polígono e que o lado [tex]\overline{AB}[/tex] do hexágono tornou-se diagonal do heptágono.
Até o momento, temos que o número de diagonais do polígono de [tex]6[/tex] lados [tex](d_{6})[/tex] mais [tex]1[/tex] formam parte do total do número de diagonais do polígono de [tex]7[/tex] lados.
No entanto, com a introdução de um novo vértice, podemos construir [tex]6[/tex] segmentos de reta com uma extremidade no vértice [tex]C[/tex] e a outra extremidade nos vértices do polígono original. Desses [tex]6[/tex] segmentos de reta, [tex]2[/tex] são os lados [tex]\overline{AC}[/tex] e [tex]\overline{BC}[/tex] do heptágono e os outros [tex]6-2=4[/tex] segmentos são diagonais do novo polígono.



Portanto, [tex]d_{7}=d_{6}+1+(6-2)[/tex], ou seja, [tex]d_{7}=d_{6}+5[/tex].

Vamos generalizar esse pensamento e encontrar uma relação de recorrência?
Imaginemos um polígono de [tex]n[/tex] lados.

Ele possui [tex]d_{n}[/tex] diagonais. Vamos construir mais um vértice [tex](C)[/tex] para esse polígono entre os vértices [tex]A[/tex] e [tex]B[/tex]. Assim, passemos para um polígono de [tex]n+1[/tex] lados.

Inicialmente, repare que as diagonais do polígono de [tex]n[/tex] lados também são diagonais desse novo polígono e que o lado [tex]\overline{AB}[/tex] do polígono original tornou-se diagonal do novo polígono. Assim, até o momento, temos que as diagonais do polígono de [tex]n[/tex] lados e o segmento [tex]\overline{AB}[/tex] são parte do total de diagonais do polígono de [tex]n+1 [/tex] lados.
No entanto, com a introdução de um novo vértice, podemos construir [tex]n[/tex] segmentos de reta com uma extremidade no vértice [tex]C[/tex] e a outra extremidade nos demais vértices do polígono original. Desses [tex]n[/tex] segmentos de reta, [tex]2[/tex] são lados do polígono de [tex]n+1[/tex] lados ([tex]\overline{AC}[/tex] e [tex]\overline{BC}[/tex]) e os outros [tex]n-2[/tex] segmentos são diagonais do novo polígono.

Portanto, [tex]d_{n+1}=d_{n}+1+(n-2)[/tex], ou seja, [tex]d_{n+1}=d_{n}+n-1[/tex]
Com isso, podemos retornar ao problema inicial e concluir que:
[tex]\qquad d_{25}=d_{24}+24-1[/tex]
[tex]\qquad \boxed{d_{25}=x+23}.[/tex]
Note que no problema não foi informado o valor de [tex]x[/tex]; mas, com a relação [tex]d_{n+1}=d_{n}+n-1[/tex] e sabendo que um triângulo não possui diagonal, podemos construir uma sequência e descobrir seu valor. É só utilizar a fórmula de recorrência abaixo.

[tex]\begin{cases} d_{n+1}=d_{n}+n-1,\, n\ge 3 \\ d_{3}=0 \end{cases}. \qquad \textcolor{#800000}{(i)}[/tex]

Você, provavelmente, deve se lembrar da fórmula para encontrar o número de diagonais de um polígono convexo de [tex]n[/tex] lados: [tex]d= \dfrac {n(n-3)}{2}\, .[/tex] Essa fórmula é dita uma forma fechada.
A grande desvantagem da forma recursiva, em relação à fechada, é que para descobrirmos termos mais avançados temos que montar a sequência definida, até o ponto desejado.
Por exemplo, no caso do polígono de [tex]24[/tex] lados em questão,

• a fórmula fechada nos fornece diretamente o número de diagonais:

[tex]\qquad d= \dfrac {24(24-3)}{2}=252;[/tex]

• para obtermos esse valor utilizando a fórmula de recorrência, teríamos que determinar sucessivamente [tex]d_4,\, d_5,\, d_6,\, \cdots\, ,\, d_{23}[/tex] para conseguirmos o valor de [tex]d_{24}.[/tex] Observe:

  [tex]\begin{array}{|c|c|}
  \hline
  \qquad n \qquad & \qquad d_n \qquad \\
  \hline
  3 & 0\\
  \hline
  \hline
  4 & 2\\
  \hline
  5 & 5\\
  \hline
  6 & 9\\
  \hline
  7 & 14\\
  \hline
  8 & 20\\
  \hline
  9 & 27\\
  \hline
  10 & 35\\
  \hline
  11 & 44\\
  \hline
  12 & 54\\
  \hline
  13 & 65\\
  \hline
  14 & 77\\
  \hline
  15 & 90\\
  \hline
  16 & 104\\
  \hline
  17 & 119\\
  \hline
  18 & 135\\
  \hline
  19 & 152\\
  \hline
  20 & 170\\
  \hline
  21 & 189\\
  \hline
  22 & 209\\
  \hline
  23 & 230\\
  \hline
  \textcolor{#589386}{24} & \, \fcolorbox{#589386}{#ddebe8}{$252$}\\
  \hline
  \end{array}[/tex]