\(\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.
Dyskretna indukcja
-
Adrian112
- Użytkownik
- Posty: 6
- Rejestracja: 22 kwie 2016, o 08:45
- Płeć: Mężczyzna
- Lokalizacja: bialystok
Dyskretna indukcja
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 .
-
szw1710
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}.}\)
-
szw1710
Dyskretna indukcja
No to skorzystaj z podanej wskazówki dot. symbolu Newtona. Odpowiednio przegrupuj sumy itp.
-
szw1710
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ę.
-
szw1710
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.
-
meursault
- 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.