Kezdőlap


Feladat:	Pontversenyen kívüli P.74	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Balog János , Bartolits István , Császár Gyula , Ferró József , Füredi Zoltán , Földvári Cs. , Geréb Mihály , Göndőcs Ferenc , Horváth Miklós , Kelen M. , Kirchner Imre , Less György , Móri Tamás , Nagy Sándor , Pressing L. , Reviczky János
Füzet:	1971/április, 170 - 171. oldal		PDF \| MathML
Témakör(ök):	Rekurzív eljárások, Fibonacci-sorozat, Számsorozatok, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1970/szeptember: Pontversenyen kívüli P.74

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.

$u_{1}$ , $u_{2}$ , $v_{1}$ , $v_{2}$ ismeretében a rekurzió alapján $u_{n}$ és $v_{n}$ , és ezért $s_{n}$ is meghatározható minden $n$ természetes számra. Azt kell tehát megvizsgálnunk, hogy $s_{1}$ , $s_{2}$ , $...$ , $s_{k - 1}$ ismerete elegendő-e $u_{1}$ , $u_{2}$ , $v_{1}$ , $v_{2}$ meghatározására. Mivel $s_{1}$ , $s_{2}$ , $...$ , $s_{k - 1}$ mindegyike kifejezhető $u_{1}$ , $u_{2}$ , $v_{1}$ , $v_{2}$ -vel (pontosabban ezek lineáris kombinációjával), azért $s_{1}$ , $s_{2}$ , $s_{3}$ , $s_{4}$ ilyen előállítása egy négyismeretlenes, elsőfokú egyenletrendszert ad $u_{1}$ , $u_{2}$ , $v_{1}$ , $v_{2}$ -re. Valóban,

\begin{matrix} s_{3} = u_{3} + v_{3} = (2 u_{2} + u_{1}) + (3 v_{2} - v_{1}), \\ s_{4} = u_{4} + v_{4} = (2 u_{3} + u_{2}) + (3 v_{3} - v_{2}) = \\ = 2 (2 u_{2} + u_{1}) + u_{2} + 3 (3 v_{2} - v_{1}) - v_{2} = 5 u_{2} + 2 u_{1} + 8 v_{2} - 3 v_{1}, \end{matrix}

így a mondott egyenletrendszer:

\begin{matrix} u_{1} & + v_{1} = s_{1}, & (1) \\ u_{2} & + v_{2} = s_{2}, & (2) \\ u_{1} + 2 u_{2} & - v_{1} + 3 v_{2} = s_{3}, & (3) \\ 2 u_{1} + 5 u_{2} & - 3 v_{1} + 8 v_{2} = s_{4} . & (4) \end{matrix}

Ezt a rendszert könnyen megoldhatjuk:

\begin{matrix} u_{1} & = - s_{2} + 3 s_{3} - s_{4}, \\ u_{2} & = - s_{1} + s_{2} + 5 s_{3} - 2 s_{4}, \\ v_{1} & = s_{1} + s_{2} - 3 s_{3} + s_{4}, \\ v_{2} & = s_{1} - 5 s_{3} + 2 s_{4} . \end{matrix}

Tehát ha

k \geq 5

, azaz legalább

s_{1}

s_{2}

s_{3}

s_{4}

adott, akkor

s_{1}

...

s_{k - 1}

-ből nemcsak

s_{k}

, de minden

s_{n} (n \geq k)

meghatározható. Ha azonban

k \leq 4

, akkor

s_{k}

nem határozható meg egyértelműen. Ha például

s_{1}

s_{2}

s_{3}

adott, de

s_{4}

már nem, akkor

(4)

-be

s_{4}

helyébe egy tetszőleges

p

számot írva, kapunk egy olyan megoldásrendszert, melyben

s_{4}

helyett mindenütt

p

áll. Azaz a megoldásrendszer más és más

p

-re más és más lesz.

Megjegyzések. 1. A kérdést természetesen úgy értettük, hogy

s_{1}

s_{2}

...

s_{k - 1}

egy helyesen képezett sorozat tagjai, nem pedig tetszés szerint választott számok. Láttuk ugyanis, hogy már

s_{1}

s_{2}

s_{3}

s_{4}

elég az

u_{n}

v_{n}

s_{n}

sorozatok visszaállítására.
2. Az

u_{n}

v_{n}

és

s_{n}

tagok rekurzív megadásából következik, hogy egyenletrendszerünk és annak megoldásrendszere helyes marad, ha bennük az indexek mindegyikéhez ugyanazt az egész számot hozzáadjuk. Következésképpen

k \geq 5

-re

\begin{matrix} u_{k - 4} & = - s_{k - 3} + 3 s_{k - 2} - s_{k - 1}, \\ u_{k - 3} & = - s_{k - 4} + s_{k - 3} + 5 s_{k - 2} - 2 s_{k - 1}, \\ (5) \\ v_{k - 4} & = s_{k - 4} + s_{k - 3} - 3 s_{k - 2} + s_{k - 1}, \\ v_{k - 3} & = s_{k - 4} - 5 s_{k - 2} + 2 s_{k - 1}, \end{matrix}

és

(4)

-ből

\begin{matrix} s_{k} & = 5 u_{k - 2} + 2 u_{k - 3} + 8 v_{k - 2} - 3 v_{k - 3} = \\ = 5 (2 u_{k - 3} + u_{k - 4}) + 2 u_{k - 3} + 8 (3 v_{k - 3} - v_{k - 4}) - 3 v_{k - 3} = \\ = 12 u_{k - 3} + 5 u_{k - 4} + 21 v_{k - 3} - 8 v_{k - 4} . \end{matrix}

Innen és

(5)

-ből könnyen adódik, hogy ha

k \geq 5

, akkor

\begin{matrix} s_{k} = s_{k - 4} - s_{k - 3} - 6 s_{k - 2} + 5 s_{k - 1} . \end{matrix}

Eszerint ha csak

s_{k}

-ra van szükségünk, ennek kiszámítása egyszerűbb, ha az ismert tagok közül a négy legnagyobb indexű tagot használjuk föl.

Móri Tamás (Budapest, Berzsenyi D. Gimn., III. o. t.)