Dyskretna indukcja
-
- Użytkownik
- Posty: 6
- Rejestracja: 22 kwie 2016, o 08:45
- Płeć: Mężczyzna
- Lokalizacja: bialystok
Dyskretna indukcja
\(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}k =n \cdot 2^{n-1}}\)
Trzeba to udowodnić indukcyjnie , jakgby ktoś mogł wytłumaczyć jak to się robi było by spoko;)
Dziekuje.
Trzeba to udowodnić indukcyjnie , jakgby ktoś mogł wytłumaczyć jak to się robi było by spoko;)
Dziekuje.
Ostatnio zmieniony 23 kwie 2016, o 18:32 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm . Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm . Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Dyskretna indukcja
Indukcję wytłumaczy ci ktoś inny, ja zaś proponuję inne rozwiązanie: ze wzoru dwumianowego Newtona mamy \(\displaystyle{ (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k.}\) Oblicz pochodną obu stron i wstaw \(\displaystyle{ x=1}\).
Kluczową w kroku indukcyjnym jest równość \(\displaystyle{ \binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.}\)
Kluczową w kroku indukcyjnym jest równość \(\displaystyle{ \binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.}\)
Dyskretna indukcja
No to skorzystaj z podanej wskazówki dot. symbolu Newtona. Odpowiednio przegrupuj sumy itp.
Dyskretna indukcja
A nie jesteś czasem na kolokwium?
Gotowców jednak tu nie dajemy. Tzn. ja nie daję.
Gotowców jednak tu nie dajemy. Tzn. ja nie daję.
Dyskretna indukcja
OK. Ale ja zaraz wychodzę na swój wykład. Dziś mówię o ekstremach funkcji dwóch zmiennych.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Dyskretna indukcja
Bo matematyka dyskretna, podobnie jak choćby zupełnie od niej odległa geometria, jest taką dziedziną, w której najważniejsze jest urodzenie i związane z tym dobre intuicje, a nie wkład pracy. Tzn. oczywiście, można się wiele nauczyć, czytając np. Matematykę konkretną (polecam, choć całej mi się nie chciało czytać) i rozwiązując zadanka, a co za tym idzie, np. zdać przedmiot na dobrą ocenę, ale generalnie jeśli się nie ma pewnego naturalnego wyczucia, to lekkości w rozwiązywaniu takich zadań się nie nabędzie (co najwyżej sprawność, a to trochę co innego).
No ale akurat indukcyjne dowodzenie różnych tożsamości jest zazwyczaj raczej schematyczne.
\(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}k=n2^{n-1}}\)
\(\displaystyle{ 1^{\circ}}\) Niech \(\displaystyle{ n=1}\). Wówczas po lewej stronie mamy \(\displaystyle{ {1\choose 0}\cdot 1=1}\), zaś po prawej \(\displaystyle{ 1\cdot 2^{0}=1}\), czyli się zgadza.
\(\displaystyle{ 2^{\circ}}\) Pokażemy, że jeśli równość zachodzi dla pewnego \(\displaystyle{ n \in \NN^{+}}\), to zachodzi również dla \(\displaystyle{ n+1}\).
\(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k= \sum_{k=1}^{n+1}{n+1 \choose k}k= \sum_{k=0}^{n}{n+1 \choose k+1}(k+1)}\)
Pierwsza równość wynika z tego, że pierwszy składnik pierwszej sumy od lewej to zero, zaś druga równość to mała zmiana indeksów - zmieniam \(\displaystyle{ k}\) pod sumą na \(\displaystyle{ k+1}\) i w związku z tym zmienia się też zakres sumy.
Następnie skorzystam ze znanej tożsamości \(\displaystyle{ {n \choose k}+{n \choose k+1}={n+1 \choose k+1}}\). Życie nie jest łatwe, udowodnij ją sam, jeśli tego nie znasz.
A zatem, wracając do naszych równości, mamy
\(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k= \sum_{k=1}^{n+1}{n+1 \choose k}k= \sum_{k=0}^{n}{n+1 \choose k+1}(k+1)=\\= \sum_{k=0}^{n}{n \choose k}(k+1)+ \sum_{k=0}^{n}{n \choose k+1}(k+1)}\)
Teraz wystarczy zapisać, że \(\displaystyle{ \sum_{k=0}^{n}{n \choose k}(k+1)= \sum_{k=0}^{n}{n \choose k}k + \sum_{k=0}^{n}{n \choose k}=n2^{n-1}+2^{n}}\)
- korzystamy z założenia indukcyjnego w celu ewaluacji \(\displaystyle{ \sum_{k=0}^{n}{n \choose k}k}\), zaś ta druga sumka to po prostu liczba podzbiorów zbioru \(\displaystyle{ n}\)-elementowego.
Ach, no i jeszcze \(\displaystyle{ \sum_{k=0}^{n}{n \choose k+1}(k+1)= \sum_{k=0}^{n-1}{n \choose k+1}(k+1)}\) (ostatni składnik był zerem, więc go wywaliłem), a dalej \(\displaystyle{ \sum_{k=0}^{n-1}{n \choose k+1}(k+1)= \sum_{k=1}^{n}{n \choose k}k=n2^{n-1}}\) - znowu przeindeksowałem, a następnie skorzystałem z założenia indukcyjnego.
Czyli pokazaliśmy, że \(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k=\sum_{k=0}^{n}{n \choose k}(k+1)+\sum_{k=0}^{n}{n \choose k+1}(k+1)}\) oraz że
\(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k=\sum_{k=0}^{n}{n \choose k}(k+1)=2^{n}+n2^{n-1}}\), a także \(\displaystyle{ \sum_{k=0}^{n}{n \choose k+1}(k+1)=n2^{n-1}}\).
Dodając stronami te dwie ostatnie równości, otrzymujemy \(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k=2^{n-1}(2n+2)=(n+1)2^{n}}\), czyli tezę indukcyjną.
Na mocy zasady indukcji matematycznej... bla bla bla, [ciach]
Ta równość ma wiele ładniejszych dowodów, no ale skoro takie jest polecenie...
-- 22 kwi 2016, o 15:35 --
Chyba właśnie dlatego wprowadzono rachunek całkowy itd. w naszym w sumie dyskretnym świecie, że liczenie sum jest za trudne. Ale akurat to zadanie tego nie obrazuje.
No ale akurat indukcyjne dowodzenie różnych tożsamości jest zazwyczaj raczej schematyczne.
\(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}k=n2^{n-1}}\)
\(\displaystyle{ 1^{\circ}}\) Niech \(\displaystyle{ n=1}\). Wówczas po lewej stronie mamy \(\displaystyle{ {1\choose 0}\cdot 1=1}\), zaś po prawej \(\displaystyle{ 1\cdot 2^{0}=1}\), czyli się zgadza.
\(\displaystyle{ 2^{\circ}}\) Pokażemy, że jeśli równość zachodzi dla pewnego \(\displaystyle{ n \in \NN^{+}}\), to zachodzi również dla \(\displaystyle{ n+1}\).
\(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k= \sum_{k=1}^{n+1}{n+1 \choose k}k= \sum_{k=0}^{n}{n+1 \choose k+1}(k+1)}\)
Pierwsza równość wynika z tego, że pierwszy składnik pierwszej sumy od lewej to zero, zaś druga równość to mała zmiana indeksów - zmieniam \(\displaystyle{ k}\) pod sumą na \(\displaystyle{ k+1}\) i w związku z tym zmienia się też zakres sumy.
Następnie skorzystam ze znanej tożsamości \(\displaystyle{ {n \choose k}+{n \choose k+1}={n+1 \choose k+1}}\). Życie nie jest łatwe, udowodnij ją sam, jeśli tego nie znasz.
A zatem, wracając do naszych równości, mamy
\(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k= \sum_{k=1}^{n+1}{n+1 \choose k}k= \sum_{k=0}^{n}{n+1 \choose k+1}(k+1)=\\= \sum_{k=0}^{n}{n \choose k}(k+1)+ \sum_{k=0}^{n}{n \choose k+1}(k+1)}\)
Teraz wystarczy zapisać, że \(\displaystyle{ \sum_{k=0}^{n}{n \choose k}(k+1)= \sum_{k=0}^{n}{n \choose k}k + \sum_{k=0}^{n}{n \choose k}=n2^{n-1}+2^{n}}\)
- korzystamy z założenia indukcyjnego w celu ewaluacji \(\displaystyle{ \sum_{k=0}^{n}{n \choose k}k}\), zaś ta druga sumka to po prostu liczba podzbiorów zbioru \(\displaystyle{ n}\)-elementowego.
Ach, no i jeszcze \(\displaystyle{ \sum_{k=0}^{n}{n \choose k+1}(k+1)= \sum_{k=0}^{n-1}{n \choose k+1}(k+1)}\) (ostatni składnik był zerem, więc go wywaliłem), a dalej \(\displaystyle{ \sum_{k=0}^{n-1}{n \choose k+1}(k+1)= \sum_{k=1}^{n}{n \choose k}k=n2^{n-1}}\) - znowu przeindeksowałem, a następnie skorzystałem z założenia indukcyjnego.
Czyli pokazaliśmy, że \(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k=\sum_{k=0}^{n}{n \choose k}(k+1)+\sum_{k=0}^{n}{n \choose k+1}(k+1)}\) oraz że
\(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k=\sum_{k=0}^{n}{n \choose k}(k+1)=2^{n}+n2^{n-1}}\), a także \(\displaystyle{ \sum_{k=0}^{n}{n \choose k+1}(k+1)=n2^{n-1}}\).
Dodając stronami te dwie ostatnie równości, otrzymujemy \(\displaystyle{ \sum_{k=0}^{n+1}{n+1 \choose k}k=2^{n-1}(2n+2)=(n+1)2^{n}}\), czyli tezę indukcyjną.
Na mocy zasady indukcji matematycznej... bla bla bla, [ciach]
Ta równość ma wiele ładniejszych dowodów, no ale skoro takie jest polecenie...
-- 22 kwi 2016, o 15:35 --
Chyba właśnie dlatego wprowadzono rachunek całkowy itd. w naszym w sumie dyskretnym świecie, że liczenie sum jest za trudne. Ale akurat to zadanie tego nie obrazuje.
Ostatnio zmieniony 23 kwie 2016, o 18:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 21
- Rejestracja: 17 lip 2015, o 18:57
- Płeć: Mężczyzna
- Lokalizacja: Zielona Góra
- Podziękował: 4 razy
- Pomógł: 1 raz
Dyskretna indukcja
Ten wzór ma dość oczywistą interpretację kombinatoryczną, gdy prawą stronę rozpatrzymy jako np. moc zbioru wszystkich drużyn z liderem wybranym spośród danych \(\displaystyle{ n}\) osób.