Analiza matematyczna, zadanie nr 2285

Autor	Zadanie / Rozwiązanie
piszczal postów: 1	2014-04-06 23:36:23 Udowodnić równanie

tumor postów: 8070	2014-04-13 22:33:25 A może być indukcyjnie? Zrozumiałe jest $\sum_{k=0}^{n}{n \choose k}1 = 2^n$, bo po obu stronach wyrażenia interpretujemy jako ilość wszystkich podzbiorów zbioru n-elementowego. Następnie $\sum_{k=0}^{n}{n \choose k}k=n2^{n-1}$ Zauważmy, że dla n=1 jest tak istotnie. Mamy $1=1$. Załóżmy zatem, że dla pewnego $n$ mamy udowodnione $\sum_{k=0}^{n}{n \choose k}k=n2^{n-1}$ i sprawdźmy, co dzieje się dla $n+1$. $\sum_{k=0}^{n+1}{n+1 \choose k}k= \sum_{k=0}^{n+1}{n \choose k}k+\sum_{k=0}^{n+1}{n \choose k-1}(k-1+1)= \sum_{k=0}^{n+1}{n \choose k}k+\sum_{k=0}^{n+1}{n \choose k-1}(k-1)+\sum_{k=0}^{n+1}{n \choose k-1}1= \sum_{k=0}^{n}{n \choose k}k+\sum_{k=0}^{n}{n \choose k}k+\sum_{k=0}^{n}{n \choose k}1= 2(n2^{n-1})+2^n=(n+1)2^{n+1-1}$ Przy tym: jeśli w wyrażeniu ${n \choose k}$ mamy $k>0$ lub $k<0$, to przyjmujemy wartość $0$ (dlatego nie sumuję do nieskończoności), w związku z tym działając na sumach przestawiam nieco indeksy, pomijając składniki zerowe, co nie wpływa na wartość sumy. Natomiast ${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$ Jeśli bowiem lewa strona oznacza liczbę k-elementowych podzbiorów zbioru n-elementowego, to wyróżniwszy jeden element $x$ tego zbioru możemy wybrać ${n-1 \choose k-1}$ podzbiorów k-1-elementowych zbioru n-1-elementowego nie zawierajacych $x$ (które po dodaniu $x$ będą $x$ zawierać i będą k-elementowe) oraz ${n-1 \choose k} $podzbiorów nie zawierających $x$ (które już są k-elementowe). To wszystkie możliwości wyboru k-el. podzbiorów zbioru n-el. Stosując identyczną metodę indukcyjną udowadniamy, że $\sum_{k=0}^{n}{n \choose k}k^2=n(n+1)*2^{n-2}$ czyli sprawdzamy dla $n=1$, następnie zakładamy n i sprawdzamy, czy wzór będzie działać dla $n+1$. Aż wreszcie dochodzimy do wzoru z treści zadania zawierającego trzecią potęgę $k$. Zaletą metody indukcyjnej jest zauważenie reguły przy kolejnych wzorach. Wadą nieco skomplikowane rachunki dla wyższych potęg. :)

tumor postów: 8070	2014-04-13 22:52:24 Jeśli nie chcemy indukcyjnie, możemy pomyśleć, co taka suma oznacza. Załóżmy, że losujemy pewien podzbiór k-el. zbioru n-el. a następnie tworzymy z elementów tego podzbioru ciąg 3-elementowy. ${n \choose k}$ to właśnie ilość losowań podzbioru, a $k^3$ to ilość ciągów 3-elementowych (z powtórzeniami), które możemy utworzyć z elementów podzbioru $k$-elementowego. Oczywiście pewne ciągi otrzymamy w ten sposób wielokrotnie, np ciąg $abc$ możemy dostać zawsze, gdy podzbiór k-elementowy zawiera elementy $a,b,c$ (niezależnie od tego, czy zawiera też inne). Zauważmy, że ciągi postaci $aaa$ (trzech jednakowych elementów) możemy uzyskać z każdego podzbioru zawierającego element $a$, mamy $2^{n-1}$ takich podzbiorów zbioru n-elementowego. Wybrany element $a$ jest jednym z $n$ elementów, zatem ogólnie ciągi z trzech jednakowych elementów dostajemy na $n2^{n-1}$ sposobów. Analogicznie ciągi postaci $aab$ $aba$ $baa$ otrzymujemy z każdego podzbioru zawierającego elementy $a,b$, jest ich $2^{n-2}$, element $a$ wybieramy na $n$ sposobów, element $b$ na $(n-1)$ sposobów (by był różny od $a$), stąd ogółem liczba $3n(n-1)2^{n-2}$ Wreszcie ciągi postaci $abc$ (trzy różne elementy) otrzymujemy z $2^{n-3}$ podzbiorów, przy tym element $a$ wybieramy na $n$ sposobów, $b$ na $n-1$, $c$ na $n-2$. Ogółem $2^{n-3}n(n-1)(n-2)$ $n2^{n-1}+3n(n-1)2^{n-2}+2^{n-3}n(n-1)(n-2)= 2^{n-3}(4n+6n(n-1)+n^3-3n^2+2n)=2^{n-3}(n^3+3n^2)$, co należało pokazać. :)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj