Kezdőlap


Feladat:	N.65	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Burcsi Péter , Pap Gyula , Szádeczky-Kardoss Szabolcs , Valkó Benedek
Füzet:	1996/január, 38. oldal		PDF \| MathML
Témakör(ök):	Teljes indukció módszere, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1995/április: N.65

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.

Legyenek a számok $a_{1} \leq a_{2} \leq ... \leq a_{n}$ . Megmutatjuk, hogy minden $k = 1$ , 2, $...$ , $n$ -re $a_{k} \leq n^{2^{k - 1}}$ . Ebből az állítás azonnal következik.
Állításunk $k = 1$ -re azt mondja, hogy $a_{1} \leq n$ . Ez nyilvánvaló, ugyanis

\begin{matrix} 1 = \frac{1}{a_{1}} + \frac{1}{a_{2}} + ... + \frac{1}{a_{n}} \leq \frac{1}{a_{1}} + \frac{1}{a_{1}} + ... + \frac{1}{a_{1}} = \frac{n}{a_{1}} . \end{matrix}

Tegyük fel, hogy állításunkat igazoltuk már minden

k \leq k_{0}

-ra (

1 \leq k_{0} < n

), azaz

1 \leq k \leq k_{0}

esetén

a_{k} \leq n^{2^{k - 1}}

. Írjuk fel

a_{1}

...

a_{k_{0}}

reciprokösszegét közönséges, tovább nem egyszerűsíthető tört alakban:

\begin{matrix} \frac{1}{a_{1}} + ... + \frac{1}{a_{k_{0}}} = \frac{A}{B} . \end{matrix}

Ez a kifejezés kisebb

1

-nél, ugyanakkor a nevezője,

B

legfeljebb akkora, mint a bal oldalon álló

a_{1}

...

a_{k_{0}}

nevezők szorzata. Ebből és az indukciós feltevésből következik, hogy

\begin{matrix} \frac{1}{a_{k_{0} + 1}} + ... + \frac{1}{a_{n}} = 1 - \frac{A}{B} \geq \frac{1}{B} \geq \frac{1}{a_{1} a_{2} ... a_{k_{0}}} \geq \frac{1}{n^{2^{0}} \cdot n^{2^{1}} \cdot ... \cdot n^{2^{k_{0} - 1}}} = \frac{1}{n^{2^{k_{0}} - 1}} . \end{matrix}

A bal oldalon álló tagok közül

\frac{1}{a_{k_{0} + 1}}

a legnagyobb, ezért

\begin{matrix} \frac{1}{n^{2^{k_{0}} - 1}} \leq \frac{1}{a_{k_{0} + 1}} + ... + \frac{1}{a_{n}} \leq \frac{n - k_{0}}{a_{k_{0} + 1}}, \end{matrix}

amiből

\begin{matrix} a_{k_{0} + 1} \leq (n - k_{0}) n^{2^{k_{0}} - 1} < n^{2^{k_{0}}} . \end{matrix}

Ezzel az állítást igazoltuk.