Udowodnij metodą indukcji

Ze względu na specyfikę metody - osobny dział.
Mr Joker
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 lis 2016, o 17:54
Płeć: Mężczyzna
Lokalizacja: Wielkopolska

Udowodnij metodą indukcji

Post autor: Mr Joker »

Hej, mam takie zadanie. Udowodnij metodą indukcji, że:
\(\displaystyle{ {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} }\)

Obliczyłem wartość dla \(\displaystyle{ k=1}\) i wyszło \(\displaystyle{ n=n}\), więc L=P.
Pomożecie z obliczeniem dla \(\displaystyle{ k=k+1}\)?
Ostatnio zmieniony 9 maja 2020, o 18:29 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Udowodnij metodą indukcji

Post autor: Jan Kraszewski »

A mógłbyś wyjaśnić, po której zmiennej robisz indukcję?

JK
Mr Joker
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 lis 2016, o 17:54
Płeć: Mężczyzna
Lokalizacja: Wielkopolska

Re: Udowodnij metodą indukcji

Post autor: Mr Joker »

Próbowałem po \(\displaystyle{ k}\).
Ostatnio zmieniony 9 maja 2020, o 18:59 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Po co cytujesz cały post, który jest tuż wyżej?
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Udowodnij metodą indukcji

Post autor: Jan Kraszewski »

I co chcesz w ten sposób udowodnić?

JK
Mr Joker
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 22 lis 2016, o 17:54
Płeć: Mężczyzna
Lokalizacja: Wielkopolska

Re: Udowodnij metodą indukcji

Post autor: Mr Joker »

To co dodałem w pierwszym poście. Taka jest treść zadania.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Udowodnij metodą indukcji

Post autor: Jan Kraszewski »

Widzisz, to nie jest takie proste. Tam są jeszcze kwantyfikatory.

Po pierwsze, zastanawiam się, po co tu indukcja. Tę równość pokazuje się w jeden linijce korzystając z definicji symbolu Newtona \(\displaystyle{ {n \choose k}=\frac{n!}{k!(n-k)!}}\). Albo w dwóch linijkach korzystając z interpretacji kombinatorycznej tegoż symbolu.

Po drugie, twierdzenie w treści zadania brzmi, formalnie rzecz biorąc, tak:

\(\displaystyle{ (\forall n\ge 1)(\forall 1\le k\le n){n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}}\) (zakładając, że \(\displaystyle{ {n-1 \choose n}=0}\)).

Indukcja po \(\displaystyle{ k}\) wygląda dość dziwnie o tyle, że musisz ustalić najpierw dowolne \(\displaystyle{ n\in\NN, n\ge 1}\) i dla tego ustalonego \(\displaystyle{ n}\) pokazywać indukcyjnie \(\displaystyle{ (\forall 1\le k\le n){n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}}\), ale wtedy jest to dość skończona wersja indukcji - pokazujesz prawdziwość \(\displaystyle{ \varphi(k)={n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}}\), gdzie \(\displaystyle{ n}\) jest ustalone, a \(\displaystyle{ k=1,...,n}\), więc indukcja urwie się po \(\displaystyle{ n}\) krokach.

Inna wersja to indukcja po \(\displaystyle{ n}\), czyli formułą dowodzoną indukcyjnie jest

\(\displaystyle{ \varphi(n)=(\forall 1\le k\le n){n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}.}\)

Ale w obu przypadkach nie bardzo widzę, jak wykorzystać "indukcyjność", bo dowód sprowadza się i tak do wykorzystania def. symbolu Newtona, a indukcja nic tutaj nie wnosi.

JK

PS
Mr Joker pisze: 9 maja 2020, o 18:27 Pomożecie z obliczeniem dla \(\displaystyle{ k=k+1}\)?
Pomożemy: \(\displaystyle{ 0=1}\) :mrgreen:
ODPOWIEDZ