Matematyka.pl

Wykaż, z indukcji atematycznej, że:

\(\displaystyle{ {n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2 ^{n}}\)

W kroku indukcyjnym skorzystaj z tego, że gdy \(\displaystyle{ k,n \in \NN, \ k< n}\), to
\(\displaystyle{ {n \choose k}+{n\choose k+1}={n+1\choose k+1}}\).

A jak rozpisać to:

\(\displaystyle{ {n + 1 \choose n + 1} = {n \choose n} + {n \choose n+ 1}}\)
\(\displaystyle{ {n + 1 \choose 0} = {n \choose -1} + {n \choose 0}}\)

Przecież te 2 działania są sprzeczne.

Nie wszystkie wyrazy trzeba rozpisać, podpowiedź to nie rozwiązanie. Korzystając z tego, co napisałem, masz:
\(\displaystyle{ {n+1\choose k}={n \choose k}+{n\choose k-1}}\) dla \(\displaystyle{ k=1,2\ldots n}\), skrajnych wyrazów, czyli \(\displaystyle{ {n+1\choose 0}}\) i \(\displaystyle{ {n+1\choose n+1}}\) nie ruszasz (zresztą nie jest to do niczego potrzebne).
Zatem:
\(\displaystyle{ {n+1\choose 0}+{n+1\choose 1}+{n+1\choose 2}\ldots+{n+1\choose n}+{n+1\choose n+1}=\\={n+1\choose 0}+\left( {n \choose 0}+{n\choose 1}+{n \choose 1}+{n\choose 2}\ldots+{n \choose n-1}+{n\choose n}\right)+{n+1\choose n+1}}\)
i teraz zauważ, że \(\displaystyle{ {n+1\choose 0}={n\choose 0}}\) oraz że \(\displaystyle{ {n+1\choose n+1}={n\choose n}}\).

Po pierwsze, nie potrzebujesz tego. Po drugie, przyjmuje się czasem, że

\(\displaystyle{ {n \choose -1}={n \choose n+ 1}=0}\)

i wtedy jest OK.

JK