Kezdőlap


Cím:	,,Bizonyítsuk be Csebysev tételét" cikksorozathoz kapcsolódó feladatok megoldása
Füzet:	1950/október, 204 - 208. oldal	PDF \| MathML

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

11. Tegyük fel, hogy $n$ és $2 n$ között nincs prímszám. Mutassuk meg, hogy akkor $(\binom{2 n}{n})$ nem lehet nagyobb, mint $2 n$ -nek annyiadik hatványa ahány prímszám van $\sqrt[]{2 n}$ -ig, megszorozva a $2 n / 3$ -ig terjedő prímszámok szorzatával.

Megoldás: Nézzük meg, hogy milyen prímszámok szerepelnek

(\binom{2 n}{n})

prímtényezős felbontásában.
A 10. feladat szerint a

\frac{2 n}{3}

és

n

közé eső prímszámok nem szerepelnek a felbontásban, a feltétel szerint pedig

n

és

2 n

között nincsenek prímszámok. Így

(\binom{2 n}{n})

felbontásában csak

\frac{2 n}{3}

-nál kisebb prímszámok szerepelnek. Ezeket osszuk két csoportra:
a) a

\sqrt[]{2 n}

-nél kisebb prímszámokra, ezek

(\binom{2 n}{n})

felbontásában szereplő hatványainak szorzata legyen

N_{1}

,
b) a

\sqrt[]{2 n}

és a

\frac{2 n}{3}

közé eső prímszámokra, ezek hatványainak szorzata legyen

N_{2}

.
Így a fentiekből következik, hogy

(\binom{2 n}{n}) = N_{1} N_{2}

.
A 8. feladat szerint minden

(\binom{2 n}{n})

felbontásában szereplő prímszámhatvány kisebb

2 n

-nél. Így, ha a

\sqrt[]{2 n}

-nél kisebb prímszámok száma

r

, akkor

\sqrt[]{N_{1}} < {(2 n)}^{r}

.
A 9. feladat szerint a

\sqrt[]{2 n}

és

\frac{2 n}{3}

közé eső prímszámok a felbontásban legfeljebb első hatványon szerepelnek, tehát

N_{2}

nem lehet nagyobb, mint az összes

\sqrt[]{2 n}

és

\frac{2 n}{3}

közé eső prímszámok szorzata:

N_{3}

.
Tehát

(\binom{2 n}{n}) = N_{1} N_{2} \leq {(2 n)}^{r} \cdot N_{3}

,
amivel az állítást igazoltuk.

12. Mutassuk meg, hogy

n \geq 14

esetén

n

-ig legfeljebb

\frac{n}{2} - 1

számú prímszám van.

Megoldás: Az állítást teljes indukcióval igazoljuk.
A 14-ig és 15-ig terjedő prímszámok száma egyaránt

6 = \frac{14}{2} - 1

és

< \frac{15}{2} - 1

, és így

n = 14

-re és

n = 15

-re a tétel fennáll.
Tegyük fel, hogy valamely

K

számra már tudjuk, hogy fennáll a tétel. Bebizonyítjuk, hogy ekkor

K + 2

-re is fennáll. Legyen

K

-ig a prímszámok száma

π (K)

. Feltétel, szerint

π (K) \leq \frac{K}{2} - 1

K + 1

és

K + 2

közül az egyik páros szám, tehát csak a másik lehet prímszám.

K + 2

-ig a prímszámok száma tehát legfeljebb 1-gyel nagyobb, mint

K

-ig, vagyis a feltétel felhasználásával:

\begin{matrix} π (K + 2) \leq π (K) + 1 < \frac{K}{2} - 1 + 1 = \frac{K + 2}{2} - 1. \end{matrix}

Ezek szerint mivel a tétel 14-re igaz, következik, hogy minden további páros számra is igaz és mivel 15-re igaz, igaz minden nagyobb páratlan számra is, tehát 14-től kezdve minden számra.

13. Mutassuk meg, hogyha

n

legalább 5, akkor

(\binom{2 n}{n})

kisebb, mint

4^{n - 1}

Megoldás: Az állítást teljes indukcióval igazoljuk.

n = 5

-re igaz a tétel, mert

(\binom{10}{5}) = 252 < 4^{4}

.
Legyen valamilyen

k

-ra igaz a tétel, vagyis

(\binom{2 k}{k}) < 4^{k - 1}

. Bebizonyítjuk, hogy ekkor

k + 1

-re is igaz a tétel. Ehhez nézzük meg, hogy

(\binom{2 k}{k})

-ból hogyan kapjuk meg

(\binom{2 (k + 1)}{k + 1})

-et.

\begin{matrix} (\binom{2 (k + 1)}{k + 1}) = \frac{(2 k + 2) (2 k + 1) (2 k) (2 k - 1) ... (k + 2)}{1 \cdot 2 ... (k + 1)} = \\ = \frac{(2 k) (2 k - 1) ... (k + 2) (k + 1)}{1 \cdot 2 ... (k + 1)} \cdot \frac{(2 k + 2) (2 k + 1)}{{(k + 1)}^{2}} = \\ = (\binom{2 k}{k}) \frac{(2 k + 2) (2 k + 1)}{{(k + 1)}^{2}} . \end{matrix}

Mivel

\frac{(2 k + 2) (2 k + 1)}{{(k + 1)}^{2}} = 2 \frac{2 k + 1}{k + 1} = 2 (2 - \frac{1}{k + 1}) < 4

így

(\binom{2 (k + 1)}{k + 1}) < 4 (\binom{2 k}{k})

A feltétel szerint

(\binom{2 k}{k}) < 4^{k - 1}, tehát (\binom{2 (k + 1)}{k + 1}) < 4^{k}

.
Ezzel állításunkat igazoltuk.

14. Mutassuk meg, hogyha egyáltalán van

n

és

2 n

között prímszám, akkor az ilyen prímszámok szorzata kisebb, mint

4^{n - 1}

Megoldás: Az

n

és

2 n

közötti prímszámok szorzata kisebb

(\binom{2 n}{n})

-nél, mert

n

és

2 n

közötti prímszámok

(\binom{2 n}{n})

számlálójában szerepelnek, nevezőjében nem így az egyszerűsítés után is megmaradnak, tehát

(\binom{2 n}{n})

-nek, mely egész szám, az

n

és

2 n

közötti prímszámok osztói, de általában ezenkívül még más törzsszámok is.
Mive1 a 13. feladatnál megmutattuk, hogy

(\binom{2 n}{n}) < 4^{n - 1}

, így az

n

és

2 n

közé eső prímszámok szorzata még inkább kisebb

4^{n - 1}

-nél.

15. Jelöljük

P_{n}

-nel az

n

számig terjedő prímszámok szorzatát. Mutassuk meg, hogy

P_{n} \leq 4^{n}

Megoldás: A tételt az előzők felhasználásával teljes indukcióval bizonyítjuk, először csak páratlan számokra.

n = 3

-ra

2 \cdot 3 = 6 < 4^{3}

, tehát igaz az állítás. (Igaz

n = 2

-re is.)
Tegyük fel tehát, hogy az egyenlőtlenséget igazoltuk már a páratlan számokra egészen

2 k - 1

-ig. Bebizonyítjuk, hogy ekkor

2 k + 1

-re is fennáll.
Válasszuk szét a

2 k + 1

-nél kisebb prímszámok szorzatát a

k + 1

-ig terjedő prímszámok szorzatára, és a

k + 1

és

2 k + 1

közötti prímszámok szorzatára. Az utóbbiról a 14. feladatból tudjuk, hogy kisebb

4^{k}

-nál. A

k + 1

-ig terjedő számokra viszont az indukciós feltevés szerint már tudjuk, hogy szorzatuk

4^{k + 1}

-nél kisebb. E kettőből viszont következik, hogy az összes

2 k + 1

-ig terjedő prímszámok szorzata kisebb, mint a fentiekből kapott

4^{k + 1} \cdot 4^{k} = 4^{2 k + 1}

érték.
Ezzel állításunkat teljes indukcióval igazoltuk páratlan

n

-ekre. Ha

n > 2

páros, akkor nem prímszám s így

n

-ig ugyanazok a prímszámok fordulnak elő, mint

n - 1

-ig, ami már páratlan, így a bebizonyított tétel szerint ezek szorzata legfeljebb

4^{n - 1}

, vagyis kisebb

4^{n}

-nél, amit bizonyítanunk kellett.

16. Tegyük fel, hogy

n

és

2 n

között nines prímszám. Mutassuk meg, hogy akkor

(\binom{2 n}{n})

nem lehet nagyobb, mint

{(2 n)}^{\frac{\sqrt[]{2 n}}{2} - 1}

4^{\frac{2 n}{3}}

feltéve, hogy

n > 100

Megoldás: A 11. feladatban láttuk, hogyha

n

és

2 n

között nincs prímszám, akkor

\begin{matrix} (\binom{2 n}{n}) \leq {(2 n)}^{r} N_{3}, \end{matrix}

(1)

ahol

r

\sqrt[]{2 n}

alatti prímszámok száma,

N_{3}

\sqrt[]{2 n}

és

\frac{2 n}{3}

közé eső prímszámok szorzata. Mivel

r

számú prímszám van

[\sqrt[]{2 n}]

-éig is, így a 12. feladat megoldása azt adja, hogy

r \leq \frac{[\sqrt[]{2 n}]}{2} - 1 \leq \frac{\sqrt[]{2 n}}{2} - 1

N_{3}

-at pedig növeljük akkor, ha nemcsak a

\sqrt[]{2 n}

és

\frac{2 n}{3}

közötti prímszámok szorzatát vesszük, hanem minden

\frac{2 n}{3}

-nál kisebb prímszám szorzatát. Ez a 15. feladat alapján nem lehet nagyobb

4^{\frac{2 n}{3}}

-nál. Így az (1) egyenlőtlenségben

{(2 n)}^{r}

N_{3}

mindkét tényezője helyett egy, legalább ugyanakkora számot írva, kapjuk, hogy

\begin{matrix} (\binom{2 n}{n}) \leq {(2 n)}^{\frac{\sqrt[]{2 n}}{2} - 1} 4^{\frac{2 n}{3}} . \end{matrix}