numeri felici

[Kocour]

Un insieme S di interi positivi è felice se il più piccolo elemento di S è anche il numero degli elementi di S. Per esempio $ \left\{2,5\right\} $ e $ \left\{3,5,9\right\} $ sono felici ma $ \left\{2,5,9\right\} $ no. Per ogni intero positivo n indichiamo con $ H_n $ il numero di sottoinsiemi felici dell'insieme $ \left\{1,2,\ldots,n\right\} $. Dimostrare che per ogni intero positivo n risulta $ H_n+H_{n+1}=H_{n+2} $.

[Pigkappa]

Mi sono bloccato a dimostrare che ;_;

$ \displaystyle \sum_{i=0}^{[0.5n]} \binom{n-1-i}{i} + \sum_{i=0}^{[0.5(n+1)]} \binom{n-i}{i} = \sum_{i=0}^{[0.5(n+2)]} \binom{n+1-i}{i} $

[LeopoldoXII]

Credo che bisogna distinguere il caso in cui n sia pari e il caso in cui è dispari

[Kocour]

Se si dimostra che $ H_n=F_n $ ($ n $-esimo numero di Fibonacci) per ogni $ n $ intero positivo, la dimostrazione è conclusa.

La relazione $ H_{n+2}=H_{n+1}+H_{n} $ si può dimostrare senza sapere cosa sono i numeri di Fibonacci e i binomiali, si inizia da $ H_{n+2} $ con $ n+2 $ ...

[Kocour]

Quanti sono i sotoinsiemi felici di $ \left\{1,\ldots,n+2\right\} $ che non contengono $ n+2 $?

[enomis_costa88]

Hum..nessuno lo vuole risolvere?

I sottinsiemi felici dell'insieme A= {1,..,n+2} contenenti n+2 sono in corrispondenza biunivoca con i sottinsiemi felici dell'insieme B= {1,...,n}.
Infatti posso fare corrispondere al sottinsieme S di A il sottinsieme G ottenuto aggiungendo uno a tutti i suoi elementi ma con un'elemento in più (n+2); e viceversa.

I sottinsiemi felici di {1,..,n+2} non contenenti n+2 sono i sottinsiemi felici di {1,...,n+1}.

Da ciò è facile concludere H_n+H_{n+1}=H_{n+2}

Buona serata, Simone.