Olimpíadas ⇒ Recorrências Tópico resolvido
Moderador: [ Moderadores TTB ]
Out 2017
23
19:35
Recorrências
Quantas são as sequências de n termos, todos pertencentes a {0,1,2}, que não possuem dois termos consecutivos iguais a zero ?
-
undefinied3 
- Mensagens: 1483
- Registrado em: Dom 02 Ago, 2015 13:51
- Última visita: 30-09-22
Out 2017
23
20:23
Re: Recorrências
Seja [tex3]f(n)[/tex3]
o número de sequências de n termos que satisfaz o que foi pedido. Temos:
[tex3]f(1)=3[/tex3] , pois as sequências são 0; 1; 2
[tex3]f(2)=8[/tex3] , são elas: 01; 02; 10; 11; 12; 20; 21; 22
Mas note: cada sequência de 1 termo que não termina em 0 dá origem à 3 outras sequências de 2, enquanto que uma sequência terminada em zero dá origem à 2 outras sequências.
Para 3 termos:
010 020 110 120 210 220
011 021 101 111 121 201 211 221
012 022 102 112 122 202 212 222
Então [tex3]f(3)=22[/tex3]
Vamos mudar de plano. Seja z(n) o total de sequências de n termos, terminadas em zero e g(n), não terminadas em zero. Assim [tex3]f(n)=z(n)+g(n)[/tex3]
Por outro lado, temos que [tex3]z(n)=g(n-1)[/tex3] e [tex3]g(n)=2g(n-1)+2z(n-1)[/tex3] , de modo que [tex3]f(n)=3g(n-1)+2z(n-1)[/tex3]
As condições iniciais são [tex3]g(1)=2[/tex3] e [tex3]z(1)=1[/tex3] . Segue o resultado:
[tex3]f(1)=3*2+2*1=8[/tex3]
[tex3]\begin{cases}
g(2)=2*2+2*1=6 \\
z(2)=2
\end{cases} \rightarrow f(3)=3*6+2*2=22[/tex3]
Agora, vamos tentar fechar a recorrência só em função de f(n):
[tex3]f(1)=3[/tex3] , [tex3]f(2)=8[/tex3]
[tex3]f(n)=3g(n-1)+2z(n-1)=3[2g(n-2)+2z(n-2)]+2g(n-2)=8g(n-2)+6z(n-2)[/tex3]
[tex3]f(n)=8[2g(n-3)+2z(n-3)]+6g(n-3)=22g(n-3)+16z(n-3)[/tex3]
[tex3]f(n-1)=3g(n-2)+2z(n-2)=3[2g(n-3)+2z(n-3)]+2g(n-3)=8g(n-3)+6z(n-3)[/tex3]
[tex3]f(n-2)=3g(n-3)+2z(n-3)[/tex3]
Então temos o sistema:
[tex3]\begin{cases}
22a+16b=f(n) \\
8a+6b=f(n-1) \\
3a+2b=f(n-2)
\end{cases}[/tex3]
Utilizando as duas últimas pra isolar a e b:
[tex3]a=3f(n-2)-f(n-1)[/tex3] [tex3]b=\frac{3f(n-1)}{2}-4f(n-2)[/tex3]
Substituindo na primeira:
[tex3]66f(n-2)-22f(n-1)+24f(n-1)-64f(n-2)=f(n)[/tex3]
[tex3]\therefore f(n)=2f(n-1)+2f(n-2)[/tex3]
De fato, [tex3]f(3)=2*8+2*3=22[/tex3]
Então fechamos a recorrência. Resta resolvê-la:
[tex3]f(n)-2f(n-1)-2f(n-2)=0[/tex3]
O polinômio característico é [tex3]x^2-2x-2=0[/tex3]
Cujas raízes são [tex3]1 \pm \sqrt{3}[/tex3]
De modo que podemos escrever [tex3]f(n)=C_1(1-\sqrt{3})^n+C_2(1+\sqrt{3})^n[/tex3]
Impondo as condições iniciais:
[tex3]\begin{cases}
C_1(1-\sqrt{3})+C_2(1+\sqrt{3})=3 \\
C_1(1-\sqrt{3})^2+C_2(1+\sqrt{3})^2=8
\end{cases}[/tex3]
Resolvendo, encontramos [tex3]C_1=\frac{1}{2}-\frac{\sqrt{3}}{3}=\frac{3-2\sqrt{3}}{6}[/tex3] e [tex3]C_2=\frac{3+2\sqrt{3}}{6}[/tex3]
Portanto, a solução geral é dada por
[tex3]f(n)=\frac{3-2\sqrt{3}}{6}(1-\sqrt{3})^n + \frac{3+2\sqrt{3}}{6}(1+\sqrt{3})^n[/tex3]
[tex3]f(1)=3[/tex3] , pois as sequências são 0; 1; 2
[tex3]f(2)=8[/tex3] , são elas: 01; 02; 10; 11; 12; 20; 21; 22
Mas note: cada sequência de 1 termo que não termina em 0 dá origem à 3 outras sequências de 2, enquanto que uma sequência terminada em zero dá origem à 2 outras sequências.
Para 3 termos:
010 020 110 120 210 220
011 021 101 111 121 201 211 221
012 022 102 112 122 202 212 222
Então [tex3]f(3)=22[/tex3]
Vamos mudar de plano. Seja z(n) o total de sequências de n termos, terminadas em zero e g(n), não terminadas em zero. Assim [tex3]f(n)=z(n)+g(n)[/tex3]
Por outro lado, temos que [tex3]z(n)=g(n-1)[/tex3] e [tex3]g(n)=2g(n-1)+2z(n-1)[/tex3] , de modo que [tex3]f(n)=3g(n-1)+2z(n-1)[/tex3]
As condições iniciais são [tex3]g(1)=2[/tex3] e [tex3]z(1)=1[/tex3] . Segue o resultado:
[tex3]f(1)=3*2+2*1=8[/tex3]
[tex3]\begin{cases}
g(2)=2*2+2*1=6 \\
z(2)=2
\end{cases} \rightarrow f(3)=3*6+2*2=22[/tex3]
Agora, vamos tentar fechar a recorrência só em função de f(n):
[tex3]f(1)=3[/tex3] , [tex3]f(2)=8[/tex3]
[tex3]f(n)=3g(n-1)+2z(n-1)=3[2g(n-2)+2z(n-2)]+2g(n-2)=8g(n-2)+6z(n-2)[/tex3]
[tex3]f(n)=8[2g(n-3)+2z(n-3)]+6g(n-3)=22g(n-3)+16z(n-3)[/tex3]
[tex3]f(n-1)=3g(n-2)+2z(n-2)=3[2g(n-3)+2z(n-3)]+2g(n-3)=8g(n-3)+6z(n-3)[/tex3]
[tex3]f(n-2)=3g(n-3)+2z(n-3)[/tex3]
Então temos o sistema:
[tex3]\begin{cases}
22a+16b=f(n) \\
8a+6b=f(n-1) \\
3a+2b=f(n-2)
\end{cases}[/tex3]
Utilizando as duas últimas pra isolar a e b:
[tex3]a=3f(n-2)-f(n-1)[/tex3] [tex3]b=\frac{3f(n-1)}{2}-4f(n-2)[/tex3]
Substituindo na primeira:
[tex3]66f(n-2)-22f(n-1)+24f(n-1)-64f(n-2)=f(n)[/tex3]
[tex3]\therefore f(n)=2f(n-1)+2f(n-2)[/tex3]
De fato, [tex3]f(3)=2*8+2*3=22[/tex3]
Então fechamos a recorrência. Resta resolvê-la:
[tex3]f(n)-2f(n-1)-2f(n-2)=0[/tex3]
O polinômio característico é [tex3]x^2-2x-2=0[/tex3]
Cujas raízes são [tex3]1 \pm \sqrt{3}[/tex3]
De modo que podemos escrever [tex3]f(n)=C_1(1-\sqrt{3})^n+C_2(1+\sqrt{3})^n[/tex3]
Impondo as condições iniciais:
[tex3]\begin{cases}
C_1(1-\sqrt{3})+C_2(1+\sqrt{3})=3 \\
C_1(1-\sqrt{3})^2+C_2(1+\sqrt{3})^2=8
\end{cases}[/tex3]
Resolvendo, encontramos [tex3]C_1=\frac{1}{2}-\frac{\sqrt{3}}{3}=\frac{3-2\sqrt{3}}{6}[/tex3] e [tex3]C_2=\frac{3+2\sqrt{3}}{6}[/tex3]
Portanto, a solução geral é dada por
[tex3]f(n)=\frac{3-2\sqrt{3}}{6}(1-\sqrt{3})^n + \frac{3+2\sqrt{3}}{6}(1+\sqrt{3})^n[/tex3]
Última edição: undefinied3 (Seg 23 Out, 2017 21:17). Total de 2 vezes.
Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 2 Respostas
- 220 Exibições
-
Última msg por FelipeMartin
