Kezdőlap


Cím:	Bizonyítsuk be Csebisev tételét 3.
Szerző(k):	Kalmár László
Füzet:	1950/május, 121 - 124. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Az alábbiakban közöljük az 1. számban kitűzött feladatok megoldását.

6. Mutassuk meg, hogy ha

a

pozitív szám, akkor

[2 a] - 2 [a]

értéke vagy

0

, vagy

1

Megoldás: Ha

a

egész szám, akkor

2 [a] = 2 a

és

[2 a] = 2 a

, tehát a vizsgálandó különbség

[2 a] - 2 [a] = 0

.
Ha

a

nem egész szám, legyen a benne foglalt legnagyobb egész szám:

[a] = a_{0}

, és így

a = a_{0} + x

ahol

0 < x < 1

2 [a]

értéke nem függ

x

-től, hanem bármely

x

-re

2 [a] = 2 a_{0}

[2 a]

értékét már befolyásolja

x

értéke, ugyanis

\begin{matrix} [2 a] = [2 (a_{0} + x)] = [2 a_{0} + 2 x] = 2 a_{0} + [2 x], \end{matrix}

tehát

\begin{matrix} [2 a] - 2 [a] = 2 a_{0} + [2 x] - 2 a_{0} = [2 x] . \end{matrix}

2 x < 1

, azaz

x < \frac{1}{2}

, akkor

[2 x] = 0

, ha

1 ≦ 2 x < 2

, azaz

\frac{1}{2} ≦ x < 1

, akkor

[2 x] = 1

7. Mutassuk meg, hogy

(\binom{2 n}{n})

mindig egész szám.

Megoldás: Határozzuk meg egy

p

prímszám kitevőjét a

(\binom{2 n}{n}) = \frac{(2 n)}{{(n!)}^{2}}

kifejezés számlálójában és nevezőjében. Ha az derül ki, hogy a számlálóban minden

p

prímszám magasabb, vagy legalább akkora kitevőn szerepel, mint a nevezőben, akkor a nevező minden tényezőjével egyszerűsíthetünk és így

(\binom{2 n}{n})

értékéül egész számot kapunk.
A számlálóban

(2 n)!

-ban egy

p

prímszám kitevője az 5. feladat megoldásából nyert Legendre-féle azonosság szerint

\begin{matrix} s_{p} = [\frac{2 n}{p}] + [\frac{2 n}{2 p^{2}}] + ... \end{matrix}

A nevezőben

{(n!)}^{2}

-ben minden

p

prímszám kitevője a kétszeres az

n!

-ban szereplő kitevőnek, vagyis

\begin{matrix} n_{p} = 2 [\frac{n}{p}] + 2 [\frac{n}{p^{2}}] + ... \end{matrix}

A számlálóban és nevezőben levő kitevők különbsége

\begin{matrix} s_{p} - n_{p} = ([\frac{2 n}{p}] - 2 [\frac{n}{p}]) + ([\frac{2 n}{p^{2}}] - 2 [\frac{n}{p}]) + ... \end{matrix}

(1)

Ez a kifejezés az előző feladatban szereplő

[2 a] - 2 [a]

alakú kifejezésnek összege. Mivel ezeknek értéke

0

vagy

1

, így összegük nem lehet negatív szám. Tehát valóban a nevezőben lévő kitevő legfeljebb akkora, mint a számlálóban lévő. Ez viszont az előzőek alapján éppen azt jelenti, hogy

(\binom{2 n}{n})

egész szám.

8. Mutassuk meg, hogy

(\binom{2 n}{n})

törzstényezős felbontásában egyik prímszám hatványa sem lehet nagyobb

2 n

-nél.

Megoldás: Nézzük meg legfeljebb hányadik hatványon fordulhat elő egy

p

prímszám. A kitevőben szereplő végtelen sok tagból álló összeg tagjai valahonnan kezdve mind

0

-val egyenlők. Honnan? Biztosan eltűnnek a tagok attól a kitevőtől kezdve, amelyre

\frac{2 n}{p^{r}} ≧ 1

és

\frac{2 n}{p^{r + 1}} < 1

. A két egyenlőtlenséget összevetve kapjuk, hogy

p^{r} ≦ 2 n < p^{r + 1}

. Tehát a fenti (1) kifejezésnek legfeljebb

r

tagja jön számításba. Ezek a tagok mind

0

-val vagy

1

-gyel egyenlők, tehát összegük legfeljebb

r

. Vagyis

p

legfeljebb

r

-edik hatványon szerepel, viszont

p^{r}

a fenti egyenlőtlenség alapján

2 n

-nél kisebb, vagy vele egyenlő.

9. Mutassuk meg, hogy

(\binom{2 n}{n})

prímfényezős felbontásában

\sqrt[]{2 n}

-nél nagyobb prímszámok legfeljebb első hatványon szerepelnek.

Megoldás: Ha

p > \sqrt[]{2 n}

, akkor már

p^{2} > 2 n

, a 7. feladatban

s_{p} - n_{p}

-nek csak egy tagja lehet, ez is vagy

0

vagy

1

, tehát

(\binom{2 n}{n})

már

p^{2}

-tel sem osztható.

10. Mutassuk meg, hogy

(\binom{2 n}{n})

nem osztható

\frac{2 n}{3}

és

n

közötti prémszámokkal, ha

n > 2

Megoldás: Az állítás bizonyítására azt kell igazolnunk, hogy minden olyan

p

prímszám, ami

\frac{2 n}{3}

és

n

között van,

(\binom{2 n}{n}) = \frac{(2 n)!}{{(n!)}^{2}}

tört számlálójában és nevezőjében ugyanazon a kitevőn szerepel.
Legyen

p

egy ilyen prímszám, akkor

2 p

nagyobb

\frac{4 n}{3}

-nál, méginkább

n

-nél, tehát

n!

tényezői közt már nem fordul elő. Így

n!

törzstényezői közt

p

az első hatványon, tehát

{(n!)}^{2}

-ben második hatványon szerepel.

(2 n)!

-ban

p

ugyancsak a második hatványon szerepel: ugyanis ha

\frac{2 n}{3} < p

akkor

3 p > 2 n

, tehát

3 p

nem szerepel a számlálóban, viszont

2 p

még előfordul, hiszen

2 p < 2 n

(2 n)!

-nek

p

-vel osztható tényezői

p

és

2 p

. Szorzatuk

2 p^{2}

, csak akkor lehet

p

-nek

2

-nél magasabb hatványával osztható, ha

p = 2

volna. Azonban

p

nagyobb

\frac{2 n}{3}

-nál, s így

n ≧ 3

folytán

p > 2

n = 2

esetén

(\binom{4}{2}) = 6

osztható

2

-vel, pedig eleget tesz a kívánt egyenlőtlenségnek.
Most már csak a 16. feladatban szereplő egyenlőtlenség megcáfolása van hátra; ha ez sikerül, akkor, legalább is

n ≧ 100

esetén, képtelenség, hogy ne legyen prímszám

n

és

2 n

között. Ezért mindenekelőtt azt nézzük meg, minél nem lehet a

(\binom{2 n}{n})

kisebb.

17. Mutassuk meg, hogy

(\binom{2 n}{n}) ≧ \frac{4^{n}}{2 n}

18. Tegyük fel ismét, hogy

n ≧ 100

és hogy

n

és

2 n

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

2^{\sqrt[]{2 n}} ≦ {(2 n)}^{\frac{3}{2}}

kellene legyen.

Ezt az egyenlőtlenséget most már nem lesz nehéz megcáfolnunk. Ugyanis legalább is valamilyen

n

-től kezdve, a baloldal nagyobb kell, hogy legyen, mint a jobboldal, hiszen

n

a baloldalon (ha gyökjel alatt is, de mégis csak) a kitevőben szerepel, a jobboldalon meg csak alapként.

19. Mutassuk meg, hogy:
a) ha

u ≧ 4

és

u

egész szám, akkor

2^{u} ≧ 3 (u + 1)

;
b) ha

u ≧ 4

, akkor

2^{u} > 3 u

(akár egész szám az

u

, akár nem);
c) ha

u ≧ 12

, akkor (megint, akár egész szám az

u

, akár nem),

2^{u} ≧ u^{3}

20. Mutassuk meg, hogy

n ≧ 100

esetén a 18. feladatban szereplő egyenlőtlenség nem állhat.

21. Mutassuk meg, hogy

n

és

2 n

között (

2 n

-et beleértve) mindig van prímszám; azaz: bizonyítsuk be Csebysev tételét.
No lám, nem is volt nehéz!