Matematyka.pl

kaminie318 pisze: ↑15 cze 2023, o 20:06 Witam. Otrzymałem zadanie o następującej treści:
Udowodnij, że \(\displaystyle{ {n\choose s} \leqslant \left( \frac{ne}{s} \right) ^{s}}\) dla wszystkich 𝑛, 𝑠 ∈ ℕ korzystając z nierówności Bernoulliego

Wykorzystując internet i źródła otrzymałem następujące wyniki. Czy może ktoś ocenić rozwiązanie?

Teza:

\[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\]

Założenia:

\[n\ \in N\ \land \text{s } \in N\ \land s \notin \{ 0\}\]

Dowód:

Aby udowodnić nierówność \[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\] można wykorzystać wzór Stirlinga.

\[L = {n\choose s} = \frac{n!}{s!(n - s)!}\]

\[{P = \left( \frac{\text{ne}}{s} \right)}^{s} = \frac{({ne)}^{s}}{s^{s}}\]

Zastępujemy n! wzorem Stirlinga:

\[L = {n\choose s} = \frac{n!}{s!(n - s)!} \approx \frac{\sqrt{2\pi n}\left( \frac{n}{e} \right)^{n}}{\sqrt{2\pi s}\left( \frac{s}{e} \right)^{s}\sqrt{2\pi(n - s)}\left( \frac{n - s}{e} \right)^{n - s}} \approx \frac{\left( \frac{n}{e} \right)^{n}}{\left( \frac{s}{e} \right)^{s}\left( \frac{n - s}{e} \right)^{n - s}} = \left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}}\]

Aby udowodnić nierówność
\[{n\choose s} \leq \left( \frac{\text{ne}}{s} \right)^{s}\]
wystarczy udowodnić, że
\[\left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}} \geq 1\]

Możemy wykorzystać nierówność arytmetyczno-geometryczną która mówi że
dla dowolnych dodatnich liczb a1, a2, a3, ....., an ich średnia geometryczna
jest mniejsza lub równa średniej arytmetycznej.

Stosując tę nierówność do \[\left( \frac{n}{e} \right)^{s}\] oraz
\[\frac{{(n - s)}^{(n - s)}}{s^{s}}\] dla \(n - s\) razy otrzymujemy:

\[\left( \left( \frac{n}{e} \right)^{s}\frac{{(n - s)}^{(n - s)}}{s^{s}} \right)^{\frac{1}{n - s + 1}} \leq \frac{\left( \frac{n}{e} \right)^{s} + \frac{{(n - s)}^{(n - s)}}{s^{s}}}{n - s + 1}\]

Można teraz wykorzystać fakt, iż \(s^{s} \leq n^{s}\)aby pokazać, że
wyrażenie po prawej stronie jest mniejsze lub równe 1:

\[\frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{s^{s}}}{n - s + 1} = \frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{n^{s}}}{n - s + 1} \leq \frac{\left( \frac{n}{e} \right)^{s} + \frac{(n - s)^{(n - s)}}{n^{s}}}{n} \leq \frac{\left( \frac{n}{e} \right)^{s} + 1}{n} \leq \frac{\frac{n}{e} + 1}{n} < 1\]

CND, dlatego \[\left( \frac{n}{s} \right) \leq \left( \frac{\text{ne}}{s} \right)^{s}\] dla wszystkich 𝑛, 𝑠 ∈ ℕ

https://pl.wikipedia.org/wiki/Wz%C3%B3r_Stirlinga#Szybko%C5%9B%C4%87_zbie%C5%BCno%C5%9Bci_i_oszacowanie_b%C5%82%C4%99du

kaminie318 pisze: ↑15 cze 2023, o 22:58 Posługuje się sztuczną inteligencją przy tym zadaniu, rzeczywiście niektóre rachunki są dziwne.

kaminie318 pisze: ↑15 cze 2023, o 23:48 Czyli rozwiązanie które tu pokazałem w ogóle nie ma sensu?

kaminie318 pisze: ↑15 cze 2023, o 23:48 Czytam odnośnik z wiki i nie rozumiem z czego wynikają hinty. Mogę prosić o bardziej szczegółowe nakierowanie?

kaminie318 pisze: ↑16 cze 2023, o 15:11

Janusz Tracz pisze: ↑16 cze 2023, o 11:10

kaminie318 pisze: ↑15 cze 2023, o 23:48 Czytam odnośnik z wiki i nie rozumiem z czego wynikają hinty. Mogę prosić o bardziej szczegółowe nakierowanie?

OK. Zignoruj wzór Stirlinga w takim razie i zrób pierwszy hint indukcją. Drugi hint nie wymaga nic poza obserwacją, że tak faktycznie jest.

Chciałem wykorzystać indukcję w tym zadaniu, nota bene takie rozwiązanie już jest na stronie jednak prowadząca zabroniła wykorzystać mi indukcję sugerując wzór Stirlinga lub wzór Taylora

kaminie318 pisze: ↑16 cze 2023, o 16:21 Czy idę dobrym tokiem myśłenia?

kaminie318 pisze: ↑17 cze 2023, o 17:06Czy wynika to z faktu, że \(\displaystyle{ s^{s} \approx s!}\)

kaminie318 pisze: ↑17 cze 2023, o 18:54 To co mi sugerujesz? Na jakiejś podstawie muszę to dowieść...

kaminie318 pisze: ↑17 cze 2023, o 18:54Próbuję teraz zrozumieć hint 2, masz jakieś wskazówki?