szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 4 kwi 2016, o 20:11 
Użytkownik

Posty: 24
Lokalizacja: warszawa
Bardzo proszę o pomoc w udowodnieniu poniższej tożsamości :)

\sum_{k=1}^{n} \ k \begin{bmatrix} n\\k\end{bmatrix}= \begin{bmatrix} n+1\\2\end{bmatrix}

Będę wdzięczna za wszelkie wskazówki!
Góra
Mężczyzna Offline
PostNapisane: 4 kwi 2016, o 20:45 
Użytkownik

Posty: 43
Lokalizacja: Warszawa
Dowód indukcyjny, bazę pominę. Załóżmy, że wzór zachodzi dla liczb mniejszych niż n.
\sum_{k=1}^nk\begin{bmatrix}n\\k\end{bmatrix}=(n-1)\sum_{k=1}^nk\begin{bmatrix}n-1\\k\end{bmatrix}+\sum_{k=1}^nk\begin{bmatrix}n-1\\k-1\end{bmatrix}=(*)
W pierwszej równości skorzystaliśmy z definicji. Teraz w pierwszej sumie możemy pominąć wyraz dla k=n, gdyż jest on równy 0, a drugą przeindeksujemy.
(*)=(n-1)\sum_{k=1}^{n-1}k\begin{bmatrix}n-1\\k\end{bmatrix}+\sum_{k=0}^{n-1}(k+1)\begin{bmatrix}n-1\\k\end{bmatrix}=(*)
Teraz w pierwszej sumie skorzystamy z założenia indukcyjnego, a drugą rozbijemy na dwie.
(*)=(n-1)\begin{bmatrix}n\\2\end{bmatrix}+\sum_{k=0}^{n-1}k\begin{bmatrix}n-1\\k\end{bmatrix}+\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}=(*)
W pierwszej sumie znów można zastosować założenie indukcyjne, a w drugiej skorzystamy z innej tożsamości dotyczącej liczb Stirlinga (której też pewnie dowodzi się indukcyjnie).
(*)=(n-1)\begin{bmatrix}n\\2\end{bmatrix}+\begin{bmatrix}n\\2\end{bmatrix}+(n-1)!=(*)
I znów skorzystamy z innej tożsamości, a następnie z definicji.
(*)=n\begin{bmatrix}n\\2\end{bmatrix}+\begin{bmatrix}n\\1\end{bmatrix}=\begin{bmatrix}n+1\\2\end{bmatrix},
co kończy dowód.
Góra
Kobieta Offline
PostNapisane: 4 kwi 2016, o 21:13 
Użytkownik

Posty: 24
Lokalizacja: warszawa
Bardzo dziękuję! Wszystko jasno rozpisane i zrozumiałe, dzięki! :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ustawianie osob w rzedzie, liczby n-cyfrowe itp  Anonymous  16
 liczby podzielne  BSD  9
 liczby podzielne - zasada wlaczania i wylaczania  BSD  3
 Liczby Bella - pytanie[nowe]  author  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl