Strona 1 z 1
Niech p(n) oznacza liczbę liczb pierwszych nie większych od liczby naturalnej n
: 6 sie 2023, o 16:47
autor: max123321
Niech \(\displaystyle{ p(n)}\) oznacza liczbę liczb pierwszych nie większych od liczby naturalnej \(\displaystyle{ n}\). Dowieść, że jeżeli \(\displaystyle{ n \ge 8}\), to \(\displaystyle{ p(n) \le \frac{n}{2}}\).
Jak to zrobić? Sprawdziłem pierwszy krok indukcyjny dla \(\displaystyle{ n=8}\) i jest to prawda, ale jak teraz w drugim kroku indukcyjnym zakładam, że \(\displaystyle{ p(n) \le \frac{n}{2} }\) i staram się pokazać, że \(\displaystyle{ p(n+1) \le \frac{n+1}{2} }\), to mam problem, bo widzę, że można zastosować szacowanie \(\displaystyle{ p(n+1) \le p(n)+1}\) i dalej z założenia indukcyjnego \(\displaystyle{ p(n+1) \le p(n)+1 \le \frac{n}{2}+1 }\), to nie dostaję tego co trzeba. Jak to poprawić?
Re: Niech p(n) oznacza liczbę liczb pierwszych
: 7 sie 2023, o 06:28
autor: Bran
Jeżeli istnieje liczba (od pewnego momentu), taka że \(\displaystyle{ p(n) \ge \frac{n}{2}}\) to istnieje najmniejsza taka liczba, oznaczmy ją \(\displaystyle{ n_0}\).
wówczas \(\displaystyle{ p(n_0) > \frac{n_0}{2}}\), ale \(\displaystyle{ p(n_0 - 1) \le \frac{n_0-1}{2},}\) wówczas
Rozważmy dwa przypadki
1. Niech \(\displaystyle{ n_0}\) będzie liczbą pierwszą, wówczas
\(\displaystyle{ p(n_0 - 1) + 1 = p(n_0)}\)
\(\displaystyle{ p(n_0) = p(n_0 - 1) + 1 \le \frac{n_0 - 1}{2} + 1 = \frac{n_0}{2} + \frac{1}{2}}\)
Ponieważ lewa strona nierówności jest liczbą naturalną, to \(\displaystyle{ p(n_0) \le \frac{n_0}{2}}\), co jest sprzeczne.
2. Niech \(\displaystyle{ n_0}\) będzie liczbą złożoną, wtedy
\(\displaystyle{ p(n_0-1) \le p(n)}\)
\(\displaystyle{ p(n_0) = p(n_0-1) \le \frac{n_0-1}{2}}\)
\(\displaystyle{ p(n_0) \le \frac{n_0}{2} - \frac{1}{2}}\)
Co również jest sprzeczne.
Re: Niech p(n) oznacza liczbę liczb pierwszych
: 7 sie 2023, o 13:13
autor: timon92
łatwiej robić indukcję ze skokiem \(2\)
dla \(n\ge 2\) wśród liczb \(n+1,n+2\) jedna jest parzysta (a zatem złożona, bo większa od \(2\)), więc wśród nich jest co najwyżej jedna liczba pierwsza
to daje \(p(n+2) \le 1+p(n)\)
ręcznie sprawdzamy, że działa dla \(n=8\) i \(n=9\) i odpalamy indukcję
Re: Niech p(n) oznacza liczbę liczb pierwszych
: 7 sie 2023, o 14:08
autor: Dasio11
Bran pisze: 7 sie 2023, o 06:28\(\displaystyle{ p(n_0) = p(n_0 - 1) + 1 \le \frac{n_0 - 1}{2} + 1 = \frac{n_0}{2} + \frac{1}{2}}\)
Ponieważ lewa strona nierówności jest liczbą naturalną, to
\(\displaystyle{ p(n_0) \le \frac{n_0}{2}}\)
To nie jest poprawny wniosek.
Re: Niech p(n) oznacza liczbę liczb pierwszych
: 8 sie 2023, o 02:12
autor: max123321
A to może być taki dowód jak przedstawił Timon92? Bo z tego co rozumiem to w tym dowodzie jakby oddzielnie sprawdzamy to twierdzenie dla liczb parzystych i oddzielnie dla nieparzystych. Bo jestem przyzwyczajony, że za pomocą indukcji udowadniamy twierdzenia po kolei dla liczb naturalnych. No, ale chyba można tak zrobić?
Re: Niech p(n) oznacza liczbę liczb pierwszych
: 8 sie 2023, o 14:33
autor: Jan Kraszewski
Jest bardzo wiele różnych wersji indukcji.
JK
Re: Niech p(n) oznacza liczbę liczb pierwszych nie większych od liczby naturalnej n
: 26 sie 2023, o 02:52
autor: Mateusz5324
max123321 pisze: 6 sie 2023, o 16:47
Niech
\(\displaystyle{ p(n)}\) oznacza liczbę liczb pierwszych nie większych od liczby naturalnej
\(\displaystyle{ n}\). Dowieść, że jeżeli
\(\displaystyle{ n \ge 8}\), to
\(\displaystyle{ p(n) \le \frac{n}{2}}\).
Jak to zrobić? Sprawdziłem pierwszy krok indukcyjny dla
\(\displaystyle{ n=8}\) i jest to prawda, ale jak teraz w drugim kroku indukcyjnym zakładam, że
\(\displaystyle{ p(n) \le \frac{n}{2} }\) i staram się pokazać, że
\(\displaystyle{ p(n+1) \le \frac{n+1}{2} }\), to mam problem, bo widzę, że można zastosować szacowanie
\(\displaystyle{ p(n+1) \le p(n)+1}\) i dalej z założenia indukcyjnego
\(\displaystyle{ p(n+1) \le p(n)+1 \le \frac{n}{2}+1 }\), to nie dostaję tego co trzeba. Jak to poprawić?
Istnieje już funkcja
\(\displaystyle{ π}\), która robi dokładnie to samo, co wprowadzona przez ciebie funkcja
\(\displaystyle{ p}\). Jeśli na coś istnieje oznaczenie, to z niego korzystajmy, a nie wymyślajmy swojego.
Pozdrawiam.
Re: Niech p(n) oznacza liczbę liczb pierwszych nie większych od liczby naturalnej n
: 26 sie 2023, o 18:00
autor: max123321
Dobra, nie wymądrzaj się.