szukanie zaawansowane
 [ Posty: 11 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 09:31 
Użytkownik

Posty: 7
Lokalizacja: bialystok
\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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 09:47 
Gość Specjalny
Avatar użytkownika

Posty: 18345
Lokalizacja: Cieszyn
Indukcję wytłumaczy ci ktoś inny, ja zaś proponuję inne rozwiązanie: ze wzoru dwumianowego Newtona mamy (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k. Oblicz pochodną obu stron i wstaw x=1.

Kluczową w kroku indukcyjnym jest równość \binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 09:51 
Użytkownik

Posty: 7
Lokalizacja: bialystok
Rozumiem indukcje , ale sęk w tym że te zadanie trzeba zrobić indukcyjnie.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 09:53 
Gość Specjalny
Avatar użytkownika

Posty: 18345
Lokalizacja: Cieszyn
No to skorzystaj z podanej wskazówki dot. symbolu Newtona. Odpowiednio przegrupuj sumy itp.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 09:59 
Użytkownik

Posty: 7
Lokalizacja: bialystok
A mógłbyś to rozwiązać ? Probowałem to robić ale zawsze mi się coś psuło ;x
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 10:01 
Gość Specjalny
Avatar użytkownika

Posty: 18345
Lokalizacja: Cieszyn
A nie jesteś czasem na kolokwium?

Gotowców jednak tu nie dajemy. Tzn. ja nie daję.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 10:08 
Użytkownik

Posty: 7
Lokalizacja: bialystok
Nie jestem... po prostu zadania podobnego typu będą na kolokwium.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 10:09 
Gość Specjalny
Avatar użytkownika

Posty: 18345
Lokalizacja: Cieszyn
OK. Ale ja zaraz wychodzę na swój wykład. Dziś mówię o ekstremach funkcji dwóch zmiennych. :)
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 10:12 
Użytkownik

Posty: 7
Lokalizacja: bialystok
Lajtowy temat , a ja dalej mam problem z dyskretną ;d
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 16:27 
Użytkownik
Avatar użytkownika

Posty: 11816
Lokalizacja: Wrocław
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.


\sum_{k=0}^{n} \binom{n}{k}k=n2^{n-1}

1^{\circ} Niech n=1. Wówczas po lewej stronie mamy {1\choose 0}\cdot 1=1, zaś po prawej 1\cdot 2^{0}=1, czyli się zgadza.
2^{\circ} Pokażemy, że jeśli równość zachodzi dla pewnego n \in \NN^{+}, to zachodzi również dla n+1.
\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 k pod sumą na k+1 i w związku z tym zmienia się też zakres sumy.
Następnie skorzystam ze znanej tożsamości {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
\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 \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 \sum_{k=0}^{n}{n \choose k}k, zaś ta druga sumka to po prostu liczba podzbiorów zbioru n-elementowego.
Ach, no i jeszcze \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 \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 \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
\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 \sum_{k=0}^{n}{n \choose k+1}(k+1)=n2^{n-1}.
Dodając stronami te dwie ostatnie równości, otrzymujemy \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.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2016, o 14:28 
Użytkownik

Posty: 21
Lokalizacja: Zielona Góra
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 n osób.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 11 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 dyskretna - nie wiem co do czego  yoyo12  4
 dyskretna rozwiązać...  dejna  2
 m dyskretna - kilka zadan, jak ugryźć  Mabakay  1
 rekurencja i indukcja porządkowa  Paragon16  1
 m dyskretna - Ile jest całkowitych rozwiązań równania .  torbol  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl