Udowodnić tożsamość

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
parchimus
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 28 maja 2020, o 18:02
Płeć: Mężczyzna
wiek: 20
Podziękował: 6 razy

Udowodnić tożsamość

Post autor: parchimus » 16 cze 2020, o 02:07

Udowodnić tożsamość rozważając ciągi złożone z liter \(\displaystyle{ a, b, c}\).

\(\displaystyle{ \sum_{k=0}^{n}\binom{n}{k}2^{n-k}=3^n}\)
Ostatnio zmieniony 16 cze 2020, o 09:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w pojedynczych tagach [latex] [/latex]. Poprawa wiadomości: rozważając.

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 2986
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 73 razy
Pomógł: 996 razy

Re: Udowodnić tożsamość

Post autor: Janusz Tracz » 16 cze 2020, o 09:36

Prawa strona to liczba ciągów długości \(\displaystyle{ n}\) złożonych z wyrazów \(\displaystyle{ \left\{ a,b,c\right\} }\). Można innymi słowy zliczać funkcje \(\displaystyle{ \omega:\left[ n\right] \rightarrow \left\{ a,b,c\right\} }\) gdzie na każde z \(\displaystyle{ n}\) miejsc można obstawiać na trzy opcje.

Po lewej mamy ten sam zbiór zliczony w inny sposób. Zauważamy, że \(\displaystyle{ \left\{ a,b,c\right\}^{\left[n \right] } }\) można rozbić na rozłączną sumę \(\displaystyle{ \left\{ a,b,c\right\}^{\left[n \right] } = \Omega_{0} \sqcup \Omega_{1} \sqcup \Omega_{2} \sqcup... \sqcup \Omega_{n} }\), gdzie \(\displaystyle{ \Omega_{k} }\) oznacza zbiór ciągów \(\displaystyle{ \omega}\) w których występuje dokładnie \(\displaystyle{ k}\) wyrazów \(\displaystyle{ a}\). Takich ciągów jest \(\displaystyle{ {n \choose k} 2^{n-k}}\) bo najpierw wybieramy dokładnie \(\displaystyle{ k}\) miejsc z pośród \(\displaystyle{ n}\) i obstawiamy wyrazem \(\displaystyle{ a}\) a następnie pozostałe \(\displaystyle{ n-k}\) miejsc obstawiamy wyrazami \(\displaystyle{ b}\) lub \(\displaystyle{ c}\) co można uczynić na \(\displaystyle{ \underbrace{2 \cdot 2 \cdot ... \cdot 2}_{n-k \text{ razy }} }\) no i ostatecznie wychodzi, że sumując ciągi z \(\displaystyle{ 0}\) wyrazów \(\displaystyle{ a}\) z \(\displaystyle{ 1}\) wyrazem \(\displaystyle{ a}\) itd. dostaniemy wszystkie ciągi. Co kończy dowód.


Można to łatwo uogólnić i pokazać, że \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} \ell^{n-k}=\left( 1+\ell\right)^n }\) dla \(\displaystyle{ \ell\in\NN}\) dokładnie w ten sam sposób.

parchimus
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 28 maja 2020, o 18:02
Płeć: Mężczyzna
wiek: 20
Podziękował: 6 razy

Re: Udowodnić tożsamość

Post autor: parchimus » 16 cze 2020, o 13:50

dziękuje, pozdrawiam!

ODPOWIEDZ