Hejka, mam do rozwiązania zadanie z indukcji matematycznej.
Udowodnić nierówność: \(\displaystyle{ \frac{4^n}{n+1} < \frac{(2n)!}{(n!)^2} }\)
dla dowolnej \(\displaystyle{ n\ge 2 }\)
Obliczyłam już pierwszy krok indukcyjny, w drugim napisałam założenie i tezę, kłopot sprawia mi jednak sam dowód. Byłabym wdzięczna z jasne rozpisanie tego dowodu, tak krok po kroku
Krok indukcyjny może wyglądać tak:
przypuśćmy, że dla pewnego \(\displaystyle{ n\in \NN, \ n\ge 2}\) zachodzi nierówność \(\displaystyle{ \frac{(2n)!}{(n!)^{2}}>\frac{4^{n}}{n+1}}\)
Mamy \(\displaystyle{ \frac{(2(n+1))!}{((n+1)!)^{2}}=\frac{(2n+2)!}{((n+1)!)^{2}}\\=\frac{(2n+2)(2n+1)}{(n+1)^{2}}\cdot \frac{(2n)!}{(n!)^{2}}\\>\frac{(2n+2)(2n+1)}{(n+1)^{2}}\cdot\frac{4^{n}}{n+1}}\)
(w ostatniej nierówności skorzystaliśmy z założenia indukcyjnego).
Jest \(\displaystyle{ \frac{4^{n+1}}{n+2}:\frac{4^{n}}{n+1}=\frac{4(n+1)}{n+2}}\), więc jeśli wykażemy, że \(\displaystyle{ \frac{(2n+2)(2n+1)}{(n+1)^{2}}\ge \frac{4(n+1)}{n+2}}\)
to będzie po herbacie. Dzieląc stronami przez dodatnie wyrażenie \(\displaystyle{ 2(n+1)}\) mamy równoważnie: \(\displaystyle{ \frac{(2n+1)}{(n+1)^{2}}\ge \frac{2}{n+2}}\)
a dalej (mnożymy stronami przez iloczyn mianowników, który oczywiście jest dodatni) \(\displaystyle{ (2n+1)(n+2)\ge 2(n+1)^{2}\\2n^{2}+5n+2\ge 2n^{2}+4n+2\\n\ge 0}\)
co jest oczywiste. Na drodze równoważnych przekształceń uzyskaliśmy prawdziwą nierówność, zatem istotnie dla \(\displaystyle{ n\in \NN, \ n\ge 2}\) jest \(\displaystyle{ \frac{(2n+2)(2n+1)}{(n+1)^{2}}\ge \frac{4(n+1)}{n+2}}\),
a zatem \(\displaystyle{ \frac{(2n+2)(2n+1)}{(n+1)^{2}}\cdot\frac{4^{n}}{n+1}\ge \frac{4^{n+1}}{n+2}}\)
co kończy krok indukcyjny.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Można też o wiele łatwiej udowodnić tezę nieindukcyjnie: ze wzoru dwumianowego Newtona mamy \(\displaystyle{ \sum_{k=0}^{n}{2n\choose k}=2^{2n}=4^{n}}\).
Po lewej stronie, w tej sumie, mamy \(\displaystyle{ n+1}\) składników, z których największym jest \(\displaystyle{ {2n\choose n}}\). Istotnie bowiem, jeśli \(\displaystyle{ 0\le k\le n-1}\), to \(\displaystyle{ {2n\choose n}:{2n\choose k}=\frac{k!(2n-k)!}{(n!)^{2}}=\frac{\frac{(2n-k)!}{n!}}{\frac{n!}{k!}}>1}\)
ponieważ po skróceniu w liczniku mamy iloczyn \(\displaystyle{ n-k}\) liczb dodatnich większych niż \(\displaystyle{ n}\), a w mianowniku iloczyn \(\displaystyle{ n-k}\) liczb dodatnich nie większych niż \(\displaystyle{ n}\).
Ponadto \(\displaystyle{ {2n\choose k}={2n\choose 2n-k}, \ 0\le k\le n}\).
Stąd wnioskujemy, że \(\displaystyle{ {2n\choose n}}\) jest największym składnikiem sumy (ostro większym od pozostałych), zatem przekracza średnią arytmetyczną składników, która wynosi właśnie \(\displaystyle{ \frac{4^{n}}{n+1}}\).
OK.
Założenie indukcyjne ma formę \(\displaystyle{ f(n)>g(n)}\),
dla funkcji \(\displaystyle{ f(x)=\frac{(2x)!}{(x!)^{2}}, \ g(x)=\frac{4^{x}}{x+1}}\).
Chcemy wykazać, że jeśli spełniona jest nierówność z założenia indukcyjnego, to zachodzi też \(\displaystyle{ f(n+1)>g(n+1)}\).
Czasami, względnie często (niekiedy trzeba postąpić subtelniej, na przykład wzmocnić w jakiś sposób tezę) można postąpić w taki sposób:
jeśli \(\displaystyle{ f,g}\) są funkcjami o wartościach dodatnich (tak jak u nas), to można zapisać \(\displaystyle{ f(n+1)=\frac{f(n+1)}{f(n)}\cdot f(n)}\)
i skorzystać tu z założenia indukcyjnego, by dostać \(\displaystyle{ f(n+1)>\frac{f(n+1)}{f(n)}\cdot g(n)}\).
My potrzebujemy z tego wydobyć \(\displaystyle{ f(n+1)>g(n+1)}\),
więc sprawa byłaby załatwiona, gdybyśmy wykazali, że \(\displaystyle{ \frac{f(n+1)}{f(n)}\cdot g(n)\ge g(n+1)}\)
a innymi słowy (podzielenie stronami przez dodatnie wyrażenie)
\(\displaystyle{ \frac{f(n+1)}{f(n)}\ge \frac{g(n+1)}{g(n)}}\)
Tutaj właśnie \(\displaystyle{ \frac{f(n+1)}{f(n)}=\frac{(2n+2)!}{((n+1)!)^{2}};\frac{(2n)!}{(n!)^{2}}=\frac{(2n+2)(2n+1)}{(n+1)^{2}}, \\ \frac{g(n+1)}{g(n)}=\frac{4^{n+1}}{n+2}:\frac{4^{n}}{n+1}=\frac{4(n+1)}{n+2}}\)
W niektórych innych zadaniach (to trzeba wyczuć, zwykle od tego zależy, czy tu występują jakieś sumy, czy iloczyny/potęgi)
lepiej wykazywać nierówność typu \(\displaystyle{ f(n+1)-f(n)\ge g(n+1)-g(n)}\) i dodać stronami do nierówności z założenia indukcyjnego w formie \(\displaystyle{ f(n)\ge g(n)}\) (bądź z ostrą nierównością).
i wtedy wykonywać działania, które doprowadzą do rozwiązania, te opisane przez Ciebie? Nie wiem czy to jest wtedy poprawnie, ale jakoś lepiej jest mi to zrozumieć wtedy.
Ostatnio zmieniony 23 lis 2020, o 18:24 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód:Poprawa wiadomości. Symbol mnożenia to \cdot.
