Kezdőlap


Feladat:	F.2242	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Danyi Pál
Füzet:	1980/október, 63. oldal		PDF \| MathML
Témakör(ök):	Rekurzív eljárások, Természetes számok, Feladat
Hivatkozás(ok):	Feladatok: 1980/február: F.2242

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.

Minden $n + 1$ jegyű szám egyértelműen előáll úgy, hogy egy $n$ jegyű végére írunk egy számjegyet. Legyen $a_{n}$ a 0-ra, $b_{n}$ az 1-re, $c_{n}$ a 2-re végződő, a feltételeknek megfelelő $n$ jegyű számok száma. Ekkor $x_{n} = a_{n} + b_{n} + c_{n}$ . Ha egy, a feltételeknek megfelelő számban az $n + 1$ -edik jegy 0, ez előtt csak 0 vagy 1 állhat, tehát

\begin{matrix} a_{n + 1} = a_{n} + b_{n} . \end{matrix}

(1)

Ha az

(n + 1)

-edik jegy 1, ezt 0, 1 és 2 egyaránt megelőzheti, tehát

b_{n + 1} = a_{n} + b_{n} + c_{n} = x_{n}

. Ezt az összefüggést még egyszer felhasználva

b_{n} = x_{n - 1}

, azaz

\begin{matrix} b_{n + 1} = a_{n} + x_{n - 1} + c_{n} . \end{matrix}

(2)

Végül 2 előtt csak 1 vagy 2 állhat, tehát

\begin{matrix} c_{n + 1} = b_{n} + c_{n} . \end{matrix}

(3)

Az (1), (2), (3) összegeként kapott összefüggés épp a bizonyítandó állítást adja:

\begin{matrix} x_{n + 1} = 2 (a_{n} + b_{n} + c_{n}) + x_{n - 1} = 2 x_{n} + x_{n - 1} . \end{matrix}

(K.M)

Danyi Pál (Pécs, Nagy Lajos Gimn., I. o. t.)