Problema interessantíssimo, não tinha parado pra fazer até que
percebi algo..
se voce for analisando a medida que os elementos
crescem no conjunto perceba:
{}----> 1
{1}---> 2
{1,2}--->3
{1,2,3}--->5
{1,2,3,4}--->8
...
os números que aparecem são os
de fibonacci e analisando a sua resolução, voce mesmo chegaria no
teorema de lucas f_n+1=Cn,0 + Cn-1,1 +Cn-2,2 +...Cn-j,j onde j é o maior
inteiro menor ou igual a n/2, o que responde sua pergunta sobre n/2.
logo é só montar a recorrência e escrever a fórmula de binet.
Espero
ter ajudado.
Douglas Oliveira!!!
On Mon, 4 Jun 2012 13:38:50 +0000,
marcone augusto araújo borges wrote:
> 1)Quantos subconjuntos do
conjunto {1,2,...,n} não contêm dois inteiros consecutivos?
>
> O vazio
seria um deles
> Com 1 elemento:n subconjuntos
> Com 2
elementos:Cn-1,2
> Com 3 elementos:Cn-2,3
> .
> .
> .
> Com n/2
elementos(se n é par):???
> Eu pensei C(n/2 + 1,n/2) = n/2 + 1...mas
isso é muito estranho,pois,se n = 10,por exemplo,só há 2 subconjuntos de
5 elementos que não contêm dois inteiros consecutivos...
> è necessario
mesmo separar em 2 casos,n par e n ímpar?
>
> 2)Qual o argumento
combinatório para mostrar que Cn,2 + Cn+1,2 = n^2?
>
> Desde já
agradeço.
