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ć?
Niech p(n) oznacza liczbę liczb pierwszych nie większych od liczby naturalnej n
-
Bran
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Re: Niech p(n) oznacza liczbę liczb pierwszych
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.
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.
-
timon92
- Użytkownik
- Posty: 1657
- Rejestracja: 6 paź 2008, o 16:47
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 7 razy
- Pomógł: 472 razy
Re: Niech p(n) oznacza liczbę liczb pierwszych
ł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ę
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ę
-
Dasio11
- Moderator
- Posty: 10227
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
-
max123321
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Re: Niech p(n) oznacza liczbę liczb pierwszych
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ć?
-
Jan Kraszewski
- Administrator
- Posty: 34296
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
-
Mateusz5324
- Użytkownik
- Posty: 47
- Rejestracja: 26 sty 2023, o 18:37
- Płeć: Mężczyzna
- wiek: 15
- Lokalizacja: Kraków
- Pomógł: 3 razy
Re: Niech p(n) oznacza liczbę liczb pierwszych nie większych od liczby naturalnej n
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.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ć?
Pozdrawiam.
