Mam udowodnić indukcyjnie, że \(\displaystyle{ 2 ^{n} = \sum_{i=0}^{n}{n \choose i} }\) oraz \(\displaystyle{ (x+1) ^{n} =\sum_{i=0}^{n} {n \choose i} x ^{i} }\), dla \(\displaystyle{ x \in \RR}\), \(\displaystyle{ n \in \NN}\).
W pierwszym nie rozumiem jednej rzeczy, więc pominę resztę dowodu.
To co teraz napiszę jest z ćwiczeń, napisane przez prowadzącego \(\displaystyle{ \sum_{i=0}^{n+1} {n+1 \choose i} = {n+1\choose 0}+ {n+1\choose 1}+...+{n+1\choose n}+{n+1\choose n+1}=2 \cdot \sum_{i=0}^{n} {n \choose i} =...}\)
I tu nie rozumiem tego przejścia. Próbowałem to rozpisywać, ale nie mam pojęcia jak tu ma wyjść, że \(\displaystyle{ \sum_{i=0}^{n+1} {n+1 \choose i} =2 \cdot \sum_{i=0}^{n} {n \choose i}}\), a ten trik kończy praktycznie zadanie.
Mówię "trik", bo brzmi, jakby było oczywiste. Dlaczego?
W drugim zapewne jest podobna zasada, dlatego nie potrafię ruszyć.
Skąd się to wzięło?
symbol Newtona w dowodzie indukcyjnym
-
- Użytkownik
- Posty: 10
- Rejestracja: 22 paź 2021, o 18:44
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 4 razy
symbol Newtona w dowodzie indukcyjnym
Ostatnio zmieniony 7 gru 2021, o 22:48 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Administrator
- Posty: 34244
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: symbol Newtona w dowodzie indukcyjnym
A korzystałeś z tego, że \(\displaystyle{ {n+1 \choose k+1} = {n \choose k} + {n \choose k+1} }\) ?
JK
JK
-
- Użytkownik
- Posty: 10
- Rejestracja: 22 paź 2021, o 18:44
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 4 razy
Re: symbol Newtona w dowodzie indukcyjnym
Skąd się to wzięło? Czuję, że powinienem to znać...
Jak w takim wypadku zastosować to do drugiego przykładu?
Jak w takim wypadku zastosować to do drugiego przykładu?
-
- Administrator
- Posty: 34244
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: symbol Newtona w dowodzie indukcyjnym
Powinieneś. To jedna z podstawowych własności symbolu Newtona.
A do pierwszego umiesz?
JK
- Janusz Tracz
- Użytkownik
- Posty: 4065
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1392 razy
Re: symbol Newtona w dowodzie indukcyjnym
Masz \(\displaystyle{ n+1}\) osób w firmie \(\displaystyle{ n}\) pracowników oraz szefa. Na ile sposobów można wybrać \(\displaystyle{ k+1}\) osobową delegację. Na \(\displaystyle{ {n+1 \choose k+1} }\). Z drugiej strony szef albo jest w delegacji albo go nie ma, gdy jest to z pozostałych \(\displaystyle{ n}\) pracowników trzeba jeszcze wybrać jeszcze \(\displaystyle{ k}\) na \(\displaystyle{ {n \choose k} }\) sposobów, a gdy szefa nie ma w delegacji to z tylko z \(\displaystyle{ n}\) pracowników wybieramy wszystkich \(\displaystyle{ k+1}\) delegatów na \(\displaystyle{ {n \choose k+1} }\) sposobów.