Quanti sottoinsiemi di {1, 2, ...., n -1, n} contengono n-1 ma non contengono n?
Quanti sottoinsiemi di {1, 2, ...., n -1, n} contengono n-1 ma non contengono n?
Banalmente 2^(n-2)
Infatti l'appartenenza di uno dei primi n-2 elementi può essere decisa in due modi (sì, o no)
per n-1 un solo modo (sì) e per n un solo modo (no)
2^(n-2)*1*1 = 2^(n-2).