Kezdőlap


Feladat:	F.3258	Korcsoport: 18-	Nehézségi fok: átlagos
Füzet:	1999/május, 289 - 290. oldal		PDF \| MathML
Témakör(ök):	Rekurzív sorozatok, Oszthatóság, Indirekt bizonyítási mód, Feladat
Hivatkozás(ok):	Feladatok: 1998/december: F.3258

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.

A definícióból nyilvánvaló, hogy az $a_{n}$ sorozat elemei egész számok. Az állítást indirekt úton fogjuk bizonyítani. Tegyük fel, hogy az $(a_{n})$ sorozat elemei között nincs 4-gyel osztható. A rekurzióból látható, hogy ha $a_{n - 1}$ páros, akkor az indirekt feltevés szerint $a_{n}$ páratlan. Ha $a_{n}$ páratlan, akkor $a_{n + 1}$ mindenképpen páros. Feltehető, hogy $a_{1}$ páratlan (ha páros volna, akkor pedig tekintsük a $(b_{n}) = (a_{n + 1})$ sorozatot, ahol $b_{1}$ páros). Ekkor minden $k \geq 1$ -re $a_{2 k - 1}$ páratlan és $a_{2 k}$ páros. Így:

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

azaz a

c_{k} = a_{2 k}

helyettesítéssel

\begin{matrix} c_{k} = \frac{3}{2} c_{k - 1} + 1, \end{matrix}

ahol nyilván a

(c_{n})

sorozat is egész elemű. A rekurziót átrendezve:

\begin{matrix} (c_{k} + 2) = \frac{3}{2} (c_{k - 1} + 2), \end{matrix}

amiből

\begin{matrix} c_{n} + 2 = {(\frac{3}{2})}^{n - 1} (c_{1} + 2), c_{n} = {(\frac{3}{2})}^{n - 1} (c_{1} + 2) - 2. \end{matrix}

c_{1} + 2

prímtényezős felbontásában 2 az

l

-edik hatványon szerepel, akkor

c_{l + 2}

már nem lehet egész szám. Ez ellentmondás, mivel láttuk, hogy a

(c_{n})

sorozat elemei egészek. Ebből következik, hogy az

(a_{n})

sorozatban van 4-gyel osztható elem.

Megjegyzés. Mindmáig bizonyítatlan az a sejtés, hogy az

(a_{n})

sorozatban előbb-utóbb előfordul az 1 (és onnantól kezdve persze az 1, 4, 2 értékek periodikusan ismétlődnek).