Ensino Médio

Mensagem não lidapor **medici** » Dom 27 Set, 2020 08:06 · Mensagem não lida por **medici** » Dom 27 Set, 2020 08:06

Use a relação de recorrência para determinar a quantidade de subconjuntos de {1,2,...,x} que não contenha dois inteiros consecutivos.

Olá:

Considere:

[tex3]F_{n}=[/tex3] número de subconjuntos que atendem as condições (nenhum elemento consecutivo)

[tex3]a_{n}=[/tex3] número de subconjuntos que atendem as condições , mas que tenham o elemento n

[tex3]b_{n}=[/tex3] número de subconjuntos que atendem as condições , mas que não tenham o elemento n

Logo:

[tex3]F_{n}=a_n+b_n[/tex3]

p/ [tex3]a_{n}[/tex3]

Perceba que todos esses subconjuntos nao podem ter o elemento n-1 , que representa assim o [tex3]b_{n-1}[/tex3]

[tex3]a_{n}=b_{n-1}[/tex3]

p/ [tex3]b_{n}[/tex3]

Perceba que todos esses subconjuntos nao podem ter o elemento n , mas podem ter o elemento n-1

O numero de subconjuntos de um conjunto que tenha até o elemento n-1 , mas que atenda as condições propostas é o proprio [tex3]F_{n-1}[/tex3]

[tex3]b_{n}=F_{n-1}[/tex3]

Abaixando o indice:

[tex3]b_{n-1}=F_{n-2}[/tex3]

Portanto,

[tex3]F_{n}=a_n+b_n=b_{n-1}+F_{n-1}=F_{n-2}+F_{n-1}[/tex3] para n maior ou igual a 3.

P/ n=1 e n=2 , voce pode fazer no braço mesmo. Com os dois primeiros termos definidos , voce encontra qualquer termo dessa recorrencia

Ensino Médio ⇒ Recorrência Tópico resolvido

Recorrência

Re: Recorrência

Ensino Médio ⇒ Recorrência Tópico resolvido

Recorrência

Re: Recorrência

Entrar • Registrar