Kezdőlap


Feladat:	Gy.2822	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Hegedűs Márton , Séllei Béla , Valkó Benedek , Vörös Zoltán
Füzet:	1993/október, 315. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Teljes indukció módszere, Másodfokú függvények, Gyakorlat
Hivatkozás(ok):	Feladatok: 1993/február: Gy.2822

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 $m$ , $f (m)$ , $f (f (m))$ , $...$ sorozat tagjait jelölje rendre $a_{0}$ , $a_{1}$ , $a_{2}$ , $...$ . Azt kell igazolnunk, hogy $i \neq j$ esetén $(a_{i}, a_{j}) = 1$ . Erre a következő összefüggésből fogunk következtetni:

\begin{matrix} tetszőleges n ⩾ 1 esetén a_{n} = (a_{0} - 1) \cdot a_{0} \cdot a_{1} \cdot ... \cdot a_{n - 2} \cdot a_{n - 1} + 1. \end{matrix}

(1)

Ez valóban elegendő a bizonyításhoz. Az általanosság megszorítása nélkül feltehető, hogy

i < j

, s ekkor (1) alapján

a_{j} = a_{i} \cdot K + 1

, ahol

K

egész szám. Legyen

(a_{j}, a_{i}) = d

. Ekkor

d | a_{j}

és

d | a_{i} \cdot K

, így

d | a_{j} - a_{i} \cdot K

, azaz

d | 1

is teljesül, ami éppen azt jelenti, hogy

(a_{i}, a_{j}) = 1

.
Most már csak az (1) formula bizonyítása van hátra. A teljes indukció módszerét alkalmazzuk. Az

n = 1

esetben

\begin{matrix} a_{1} = f (m) = f (a_{0}) = a_{0}^{2} - a_{0} + 1 = (a_{0} - 1) a_{0} + 1, \end{matrix}

s ez pontosan az állítás.
Tegyük föl, hogy (1) igaz

n = k - 1

-re, és vizsgáljuk az

n = k

esetet. Ekkor

\begin{matrix} a_{k} = f (a_{k - 1}) = a_{k - 1}^{2} - a_{k - 1} + 1 = (a_{k - 1} - 1) a_{k - 1} + 1. \end{matrix}

(2)

Az indukciós feltevés szerint

\begin{matrix} a_{k - 1} - 1 = (a_{0} - 1) a_{0} a_{1} ... a_{k - 3} a_{k - 2} + 1 - 1 = (a_{0} - 1) a_{0} a_{1} ... a_{k - 3} a_{k - 2}, \end{matrix}

ezt beírva (2)-be

\begin{matrix} a_{k} = (a_{0} - 1) a_{0} a_{1} ... a_{k - 3} a_{k - 2} a_{k - 1} + 1, \end{matrix}

és éppen ezt kellett igazolni.

Hegedűs Márton (Főv. Fazekas M. Gyak. Gimn., I. o. t.) dolgozata alapján