Zadanie z indukcji matematycznej, udowodnić nierówność
-
- Użytkownik
- Posty: 5
- Rejestracja: 22 lis 2020, o 22:05
- Płeć: Kobieta
- wiek: 20
- Podziękował: 3 razy
Zadanie z indukcji matematycznej, udowodnić nierówność
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
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
-
- Administrator
- Posty: 34543
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 4 razy
- Pomógł: 5226 razy
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Zadanie z indukcji matematycznej, udowodnić nierówność
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}}\).
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}}\).
-
- Użytkownik
- Posty: 5
- Rejestracja: 22 lis 2020, o 22:05
- Płeć: Kobieta
- wiek: 20
- Podziękował: 3 razy
Re: Zadanie z indukcji matematycznej, udowodnić nierówność
\(\displaystyle{ \frac{4^{n+1}}{n+2}:\frac{4^{n}}{n+1}=\frac{4(n+1)}{n+2}}\)
Mam jeszcze pytanie, nie wiem skąd się wzięło tutaj dzielenie
Mam jeszcze pytanie, nie wiem skąd się wzięło tutaj dzielenie
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Zadanie z indukcji matematycznej, udowodnić nierówność
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ą).
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ą).
-
- Użytkownik
- Posty: 5
- Rejestracja: 22 lis 2020, o 22:05
- Płeć: Kobieta
- wiek: 20
- Podziękował: 3 razy
Re: Zadanie z indukcji matematycznej, udowodnić nierówność
Wielkie dzięki za zadanie, teraz muszę to przyswoić i zrozumieć
A czy mogę rozpisać tezę na stronę L i P doprowadzić ją do jak najprostszej postaci korzystając z założenia, i znowu wziąć to w nierówność?
\(\displaystyle{ T: \frac{4 ^{n+1} }{n+2} \le \frac{(2n+2)!}{((n+1)!)^2} }\)
\(\displaystyle{ P: \frac{(2n+2)!}{((n+1)!)^2} = \frac{(2n)!(2n+1)(2n+2)}{n!(n+1)^2} = \frac{(2n)!}{(n!)^2} \cdot \frac{(2n+1)(2n+2)}{(n+1)^2} > \frac{(2n+1)(2n+2)}{(n+1)^2} \cdot \frac{4^n}{(n+1)} }\) to z założenia indukcyjnego
\(\displaystyle{ L: \frac{4^n+1}{n+2} = 4^n \cdot \frac{4}{n+2} }\)
\(\displaystyle{ 4^n \cdot \frac{4}{n+2} < \frac{(2n+1)(2n+2)}{(n+1)^2} \cdot \frac{4^n}{(n+1)} }\)
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.
A czy mogę rozpisać tezę na stronę L i P doprowadzić ją do jak najprostszej postaci korzystając z założenia, i znowu wziąć to w nierówność?
\(\displaystyle{ T: \frac{4 ^{n+1} }{n+2} \le \frac{(2n+2)!}{((n+1)!)^2} }\)
\(\displaystyle{ P: \frac{(2n+2)!}{((n+1)!)^2} = \frac{(2n)!(2n+1)(2n+2)}{n!(n+1)^2} = \frac{(2n)!}{(n!)^2} \cdot \frac{(2n+1)(2n+2)}{(n+1)^2} > \frac{(2n+1)(2n+2)}{(n+1)^2} \cdot \frac{4^n}{(n+1)} }\) to z założenia indukcyjnego
\(\displaystyle{ L: \frac{4^n+1}{n+2} = 4^n \cdot \frac{4}{n+2} }\)
\(\displaystyle{ 4^n \cdot \frac{4}{n+2} < \frac{(2n+1)(2n+2)}{(n+1)^2} \cdot \frac{4^n}{(n+1)} }\)
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.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 5
- Rejestracja: 22 lis 2020, o 22:05
- Płeć: Kobieta
- wiek: 20
- Podziękował: 3 razy
Re: Zadanie z indukcji matematycznej, udowodnić nierówność
Dzięki jeszcze raz, jestem bardzo wdzięczna