dowód kombinatoryczny równości

[strzyga]

Proszę o pomoc w rozwiązaniu zadania. Uczę się do poprawki z kombinatoryki a udowadnianie nie bardzo mi idzie...

zadanie:

Udowodnij kombinatorycznie równość dla \(\displaystyle{ n \ge 3}\)

\(\displaystyle{ \sum_{k=1}^{n} (2 ^{n-k} -1)=2 ^{n} -(n+1)}\)

[bartek118]

Z lewej strony - ustalmy k. Wówczas \(\displaystyle{ 2^{n-k}-1}\) to ilość podzbiorów zbioru (n-k)-elementowego, bez zbioru pustego. A zatem lewa strona zlicza wszystkie podzbiory o dowolnej liczbie elementów, przy czym zbiór pusty jest odejmowany dokładnie n razy (bo k=1..n) oraz nie jest nigdy liczony cały zbiór n-elementowy (bo k nie jest nigdy równe 0). Ponieważ wszystkich podzbiorów zbioru n-elementowego jest \(\displaystyle{ 2^{n}}\), to po odjęciu n razy zbioru pustego i jeden raz całego n-elementowego zbioru otrzymujemy \(\displaystyle{ 2^{n}-(n+1)}\), czyli prawą stronę równości.

[MichalKulis]

@bartek - popełniasz błąd logiczny. po lewej stronie zliczasz wszystkie niepuste podzbiory zbiorów mocy od n-1 do 0. Natomiast po prawej stronie liczysz wszystkie podzbiory zbioru mocy n. A to nie to samo.

proponuję tak:

\(\displaystyle{ L = \sum_{k=1}^{n} 2^{n-k} - \sum_{k=1}^{n} 1 = -n + 2^{n} \sum_{k=1}^{n} (\frac{1}{2}) ^{k} = -n + 2^{n} \cdot (1- (\frac{1}{2})^{n}) = -n + 2 ^{n} -1 = P}\)