Suma dwumianów Newtona

[fart411]

\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^{n}}\) - mam do udowodnienia taką równość. Znalazłem jakiś dowód, ale nie wiem czy jest on prawidłowy (nie rozumiem w nim pewnych przekształceń.
Wygląda on tak: dla\(\displaystyle{ n=1}\) ta suma jest równa \(\displaystyle{ 2=2^{1}}\)
Założenie indukcyjne: dla \(\displaystyle{ n=l: \sum_{k=0}^{l} {l \choose k} = 2^{l}}\)
Dla \(\displaystyle{ n=l+1:}\)
\(\displaystyle{ \sum_{k=0}^{l+1} {l+1 \choose k} = \sum_{k=0}^{l+1} {l \choose k} + {l \choose k-1}= (\sum_{k=0}^{l} {l \choose k} + {l \choose k-1}) +{l+1 \choose 0} + {l+1 \choose l+1} = \sum_{k=0}^{l} {l \choose k} + \sum_{k=0}^{l+1} {l \choose k-1}=2^{l}+2^{l}=2^{l+1}}\)

Czy jest on dobry? Jeśli tak to skąd wzięło się przekształcenie \(\displaystyle{ \sum_{k=0}^{l+1} {l+1 \choose k} = \sum_{k=0}^{l+1} {l \choose k} + {l \choose k-1}}\)? Proszę o wyjaśnienie.

[Errichto]

Jeśli masz wybrać ze 100 elementów jakieś 6, to oznaczasz któryś z setki jako np. X i szóstka do wybrania może zawierać X-a albo nie. Jeśli nie zawiera, to z 99 wybieramy 6 elementów. Jeśli zawiera, to z 99 wybieramy 5 elementów. Stąd:
\(\displaystyle{ {100 \choose 6}= {99 \choose 6} + {99 \choose 5} \\ {a \choose b} = {a-1 \choose b} + {a-1 \choose b-1}}\)
czyli też:
\(\displaystyle{ \sum_{k=0}^{l+1} {l+1 \choose k} = \sum_{k=0}^{l+1}( {l \choose k} + {l \choose k-1})}\)
A ogólnie sposób rozwiązania dziwny i błędny chyba. To:
\(\displaystyle{ ...+{l+1 \choose 0} + {l+1 \choose l+1}}\)
na pewno prawidłowe nie jest.
Proponuję takie dowody:
1.

Ukryta treść:    

Indukcyjny. Z \(\displaystyle{ n}\) wybieramy \(\displaystyle{ 0}\) elementów lub \(\displaystyle{ 1}\) lub \(\displaystyle{ 2}\) lub ... lub \(\displaystyle{ n}\). Czyli te \(\displaystyle{ 2^n}\) to ogólnie liczba jakkolwiek licznych podzbiorów zbioru \(\displaystyle{ n}\)-elementowego. Następnie szukamy liczby podzbiorów \(\displaystyle{ n+1}\)-elementowego zbioru. Jeśli ostatni element jest wybrany, to poprzednie możemy wybrać na \(\displaystyle{ 2^n}\) sposobów (z założenia indukcyjnego). Jeśli nie to znowu na \(\displaystyle{ 2^n}\) sposobów wybieramy resztę. Razem \(\displaystyle{ 2^n+2^n=2^{n+1}}\)

2.

Ukryta treść:    

Bez indukcji. Jak w poprzednim zauważamy, że ta suma to liczba podzbiorów zbioru \(\displaystyle{ n}\)-elementowego. Każdy element może być w podzbiorze albo nie być. 2 możliwości. I tak jest z wszystkimi \(\displaystyle{ n}\) elementami. Czyli łącznie \(\displaystyle{ 2^n}\) sposobów.