Analiza matematyczna, zadanie nr 2285
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
piszczal post贸w: 1 |  2014-04-06 23:36:23Udowodni膰 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=n*2^{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=n*2^{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*(n*2^{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 $n*2^{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 $3*n*(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)$ $n*2^{n-1}+3*n*(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