wyznaczyć liczbę podzbiorów
: 24 cze 2010, o 13:49
wyznaczyć liczbę podzbiorów zbioru \(\displaystyle{ \{0,1...n\}}\), które nie zawierają żadnych dwóch kolejnych liczb. tylko tak z wytłumaczeniem proszę ;D
Jeśli \(\displaystyle{ a_{n}}\) oznacza szukaną liczbę podzbiorów zbioru \(\displaystyle{ \{1,2,3,...,n\}}\), to \(\displaystyle{ a_{n}=a_{n-1}+a_{n-2}}\).
Dlaczego? Podzbiorów spełniających zadany warunek, niezawierających \(\displaystyle{ n}\), jest oczywiście \(\displaystyle{ a_{n-1}}\). Do tej liczby musimy dodać liczbę podzbiorów tego zbioru spełniających dany warunek i zawierających n. Wszystkie takie podzbiory tworzymy, dokładając liczbę n do każdego z \(\displaystyle{ a_{n-2}}\) spełniających warunek podzbiorów zbioru \(\displaystyle{ \{1,2,...,n-2\}}\) (bierze się to stąd, że podzbiory, do których dokładamy \(\displaystyle{ n}\), nie mogą zawierać \(\displaystyle{ n-1}\)).
Po rozwiązaniu tej rekurencji (uwzględniamy \(\displaystyle{ a_{0}=2,a_{1}=3}\)), otrzymujemy: \(\displaystyle{ a_{n}= \frac{2\sqrt{5}+5}{5} \cdot \left(\frac{1+\sqrt{5}}{2}\right)^{n} + \frac{5-2\sqrt{5}}{5} \cdot \left(\frac{1-\sqrt{5}}{2}\right)^{n}}\).