Feladat:	Pontversenyen kívüli P.354	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Csikós Zsolt ,  Drávucz Katalin ,  Fritz Péter ,  Hajós Zsuzsanna ,  Holbok István ,  Jenei Attila ,  Lenkó Csaba ,  Megyesi Gábor ,  Nádor Péter ,  Nagy 548 Róbert ,  Németh Attila ,  Takács Gábor ,  Tranta Beáta ,  Weisz Ferenc ,  Wolfgang Moldenhauer
Füzet:	1982/november, 147 - 150. oldal		PDF  |  MathML
Témakör(ök):	Számsorozatok, Teljes indukció módszere, Pontversenyen kívüli probléma, Rekurzív sorozatok
Hivatkozás(ok):	Feladatok: 1981/november: Pontversenyen kívüli P.354

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. $\begin{array}{c}{\displaystyle a_0=a_1=\mathrm{1,}}\end{array}$ (1) $\begin{array}{c}{\displaystyle a_{n+1}=2a_n+a_{n-1}\left(n=\mathrm{1,2,}\text{...}\right)\mathrm{.}}\end{array}$ (2) I. megoldás. Számitsuk ki az $a_0\mathrm{,}{a}_1\mathrm{,}\text{...}$ sorozat első pár tagját: $\begin{array}{c}{\displaystyle a_0=a_1=\mathrm{1,}{a}_2=\mathrm{3,}{a}_3=\mathrm{7,}{a}_4=\mathrm{17,}{a}_5=\mathrm{41,}{a}_6=\mathrm{99,}{a}_7=\mathrm{239,}\text{ és }{a}_8=577.}\end{array}$ Ha a $2\left(a_{2n}^2-1\right)$ kifejezés értékét is kiszámítjuk $n=\mathrm{1,2,3,4}$-re, akkor azt kapjuk, hogy $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cccc}{\displaystyle 2\left(a_2^2-1\right)=}\hfill & \hfill {\displaystyle 16=}& \hfill {\displaystyle 4^2=}& {\displaystyle {\left(1+3\right)}^2}\hfill \\ {\displaystyle 2\left(a_4^2-1\right)=}\hfill & \hfill {\displaystyle 576=}& \hfill {\displaystyle {24}^2=}& {\displaystyle {\left(7+17\right)}^2}\hfill \\ {\displaystyle 2\left(a_6^2-1\right)=}\hfill & \hfill {\displaystyle 19600=}& \hfill {\displaystyle {140}^2=}& {\displaystyle {\left(41+99\right)}^2}\hfill \\ {\displaystyle 2\left(a_8^2-1\right)=}\hfill & \hfill {\displaystyle 665856=}& \hfill {\displaystyle {816}^2=}& {\displaystyle {\left(239+577\right)}^2\mathrm{.}}\hfill \end{array}}}\end{array}$ Valószínűnek látszik tehát, hogy általában igaz a $\begin{array}{c}{\displaystyle 2\left(a_{2n}^2-1\right)={\left(a_{2n}+a_{2n-1}\right)}^2}\end{array}$ (3) összefüggés. Ezt fogjuk most teljes indukcióval belátni. Láttuk, hogy $n=\mathrm{1,2}$-re (3) teljesül. Tegyük most fel, hogy $k\geqq 2$ és $2n=2k-2$-re igaz a fenti összefüggés, azaz $\begin{array}{c}{\displaystyle 2\left(a_{2k-2}^2-1\right)={\left(a_{2k-2}+a_{2k-3}\right)}^2\mathrm{.}}\end{array}$ (4) Ebből akarjuk bebizonyítani, hogy $\begin{array}{c}{\displaystyle 2\left(a_{2k}^2-1\right)={\left(a_{2k}+a_{2k-1}\right)}^2}\end{array}$ (5) is fennáll. Vonjuk ki (5) bal oldalából (4) bal oldalát: A különbség $2\left(a_{2k}^2-a_{2k-2}^2\right)=2\left(a_{2k}-a_{2k-2}\right)\left(a_{2k}+a_{2k-2}\right)$. Az első zárójelben (2) szerint $2a_{2k-1}$ áll, tehát (5) és (4) bal oldalának különbsége $4a_{2k-1}\left(a_{2k}+a_{2k-2}\right)$. Másrészt a jobb oldalak különbsége $\begin{array}{c}{\displaystyle \left(a_{2k}+a_{2k-1}+a_{2k-2}+a_{2k-3}\right)\left(a_{2k}+a_{2k-1}-a_{2k-2}-a_{2k-3}\right)\mathrm{.}}\end{array}$ Az első tényezőnél $a_{2k}$-ra, majd $a_{2k-2}$-re alkalmazva a (2) összefüggést, azt kapjuk, hogy $\begin{array}{c}{\displaystyle a_{2k}+a_{2k-1}+a_{2k-2}+a_{2k-3}=3a_{2k-1}+2a_{2k-2}+a_{2k-3}=4a_{2k-1}\mathrm{.}}\end{array}$ A második tényezőben $a_{2k-1}-a_{2k-2}-a_{2k-3}=a_{2k-2}$ [most $a_{2k-2}$-re alkalmaztuk (2)-t]. A két jobb oldal különbsége tehát $4a_{2k-1}\left(a_{2k}+a_{2k-2}\right)$. Látjuk tehát, hogy (5) és (4) bal oldalának különbsége megegyezik a két jobb oldal különbségével. Minthogy (4) az indukciós feltevés szerint igaz, ebből következik, hogy (5) is igaz. Ezzel az indukciós lépést, s egyszersmind (3)-at is bebizonyítottuk. Minthogy pedig $a_{2k}+a_{2k-1}$ minden $k$-ra természetes szám, ezzel azt is beláttuk, hogy $2\left(a_{2k}^2-1\right)$ minden természetes számra teljes négyzet.   II. megoldás. (3) felírható úgy is, hogy $\begin{array}{c}{\displaystyle 2a_{2n}^2-{\left(a_{2n}+a_{2n-1}\right)}^2=2.}\end{array}$ (3$\text{'}$) Be fogjuk látni, hogy ha $a_0$, $a_1$ tetszőleges számok és $n\geqq 1$-re $a_{n+1}$-et a (2) egyenlet definiálja, akkor minden $n\geqq 2$-re $\begin{array}{c}{\displaystyle 2a_{2n}^2-{\left(a_{2n}+a_{2n-1}\right)}^2=2a_{2n-2}^2-{\left(a_{2n-2}+a_{2n-3}\right)}^2\mathrm{.}}\end{array}$ (6) Ebből már következik, hogy $2a_{2n}^2-{\left(a_{2n}+a_{2n-1}\right)}^2$ értéke független $n$-től és megegyezik $2a_2^2-{\left(a_2+a_1\right)}^2$ értékével. A feladat esetében ez az érték éppen $2$, mert $a_1=1$, $a_2=3$. Ha tehát belátjuk, hogy minden $a_n$ sorozatra, amelyre (2) teljesül, (6) is teljesül, ebből (3$\text{'}$) és a feladat állítása már következik. Jelöljük $u$-val $a_{2n-2}$-t és $v$-vel $a_{2n-2}+a_{2n-3}$-at. Próbáljuk meg $a_{2n}$-t és $\left(a_{2n}+a_{2n-1}\right)$-et kifejezni $u$-val és $v$-vel! Ehhez a (2) egyenletet használjuk: $\begin{array}{c}{\displaystyle a_{2n}=2a_{2n-1}+a_{2n-2}=2\left(2a_{2n-2}+a_{2n-3}\right)+a_{2n-2}=3u+2v}\end{array}$ $\begin{array}{c}{\displaystyle a_{2n}+a_{2n-1}=3a_{2n-1}+a_{2n-2}=3\left(2a_{2n-2}+a_{2n-3}\right)+a_{2n-2}=4u+3v\mathrm{.}}\end{array}$ (6) tehát azt állítja, hogy $\begin{array}{c}{\displaystyle 2{\left(3u+2v\right)}^2-{\left(4u+3v\right)}^2=2u^2-v^2\mathrm{,}}\end{array}$ ami minden $u$, $v$ számpárra fennáll. Beláttuk tehát, hogy a (2) egyenletből (6) minden $n\geqq 2$-re következik, ami bizonyítandó volt.   III. megoldás. Próbáljuk meg $a_n$-t $c{\lambda }^n+d{\mu }^n$ alakban felírni, ahol $c$, $d$, $\lambda$, $\mu$ alkalmas konstansok. $a_n$-re teljesül a (2) egyenlet, ami azt jelenti, hogy minden $n$-re teljesülnie kell a $\begin{array}{c}{\displaystyle c{\lambda }^n+d{\mu }^n=2c{\lambda }^{n-1}+2d{\mu }^{n-1}+c{\lambda }^{n-2}+d{\mu }^{n-2}}\end{array}$ egyenlőségnek. Átalakítások után azt kapjuk, hogy minden $n$-re $\begin{array}{c}{\displaystyle c{\lambda }^{n-2}\left({\lambda }^2-2\lambda -1\right)+d{\mu }^{n-2}\left({\mu }^2-2\mu -1\right)=0.}\end{array}$ Ha most $\mu$-t és $\lambda$-t az $x^2-2x-1=0$ másodfokú egyenlet két gyökének, $\left(1+\sqrt[]{2}\right)$-nek, ill. $\left(1-\sqrt[]{2}\right)$-nek választjuk, ez mindig teljesülni fog. Ha tehát $a_n=c{\left(1+\sqrt[]{2}\right)}^n+d{\left(1-\sqrt[]{2}\right)}^n$, akkor a (2) egyenlet minden $n$-re teljesül. Szükségünk van még arra is, hogy $a_0=1$ és $a_1=1$ legyen, azaz $\begin{array}{c}{\displaystyle c{\left(1+\sqrt[]{2}\right)}^0+d{\left(1-\sqrt[]{2}\right)}^0=c+d=1\text{ és }c\left(1+\sqrt[]{2}\right)+d\left(1-\sqrt[]{2}\right)=1}\end{array}$ is teljesüljön. A két egyenletet $c$-re, $d$-re megoldva azt kapjuk, hogy $c=d=1/2$. Következésképp az $\begin{array}{c}{\displaystyle a{\text{'}}_n=\frac{1}{2}\left({\left(1+\sqrt[]{2}\right)}^n+{\left(1-\sqrt[]{2}\right)}^n\right)n=\mathrm{0,1,2,}\text{...}}\end{array}$ képlettel definiált sorozatra teljesül, hogy $\begin{array}{c}{\displaystyle a_0\text{'}=a_1\text{'}=1\text{ és }{a}_{n+1}\text{'}=2a_n\text{'}+a_{n-1}\text{'}n=\mathrm{1,2,}\text{...}\mathrm{.}}\end{array}$ Teljes indukcióval azonnal látható, hogy az $a_n\text{'}$ sorozat megegyezik a feladatban definiált $a_n$ sorozattal. Azt kaptuk tehát, hogy $\begin{array}{c}{\displaystyle a_n=\frac{1}{2}\left({\left(1+\sqrt[]{2}\right)}^n+{\left(1-\sqrt[]{2}\right)}^n\right)\mathrm{.}}\end{array}$ (7) (Megjegyzendő, hogy a jobb oldalon ‐ bár ez az első pillanatban nem látszik ‐ egész szám áll.) A feladat állítása mármost az, hogy $2\left(a_{2n}^2-1\right)$ teljes négyzet. (7) szerint ${\displaystyle \begin{array}{cc}\hfill {\displaystyle 2\left(a_{2n}^2-1\right)}& {\displaystyle =2\left[\frac{1}{4}{\left({\left(1+\sqrt[]{2}\right)}^{2n}+{\left(1-\sqrt[]{2}\right)}^{2n}\right)}^2-1\right]=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\frac{1}{2}\left[{\left(1+\sqrt[]{2}\right)}^{4n}+{\left(1-\sqrt[]{2}\right)}^{4n}\right]+\frac{2\cdot 2\cdot {\left(1+\sqrt[]{2}\right)}^{2n}{\left(1-\sqrt[]{2}\right)}^{2n}}{4}-2=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\frac{1}{2}\left[{\left(1+\sqrt[]{2}\right)}^{4n}+{\left(1-\sqrt[]{2}\right)}^{4n}\right]-1={\left(\frac{{\left(1+\sqrt[]{2}\right)}^{2n}-{\left(1-\sqrt[]{2}\right)}^{2n}}{\sqrt[]{2}}\right)}^2\mathrm{.}}\hfill \end{array}}$ Azt kell tehát belátnunk, hogy a nagy zárójelben egész szám áll. A binomiális tétel szerint $\begin{array}{c}{\displaystyle {\left(1+\sqrt[]{2}\right)}^{2n}=1+\left(\genfrac{}{}{0ex}{}{2n}{1}\right)\sqrt[]{2}+\left(\genfrac{}{}{0ex}{}{2n}{2}\right){\sqrt[]{2}}^2+\left(\genfrac{}{}{0ex}{}{2n}{3}\right){\sqrt[]{2}}^3+\text{...}+\left(\genfrac{}{}{0ex}{}{2n}{2k}\right){\sqrt[]{2}}^{2k}+\left(\genfrac{}{}{0ex}{}{2n}{2k+1}\right){\sqrt[]{2}}^{2k+1}+\text{...}+{\sqrt[]{2}}^{2n}}\end{array}$ $\begin{array}{c}{\displaystyle {\left(1-\sqrt[]{2}\right)}^{2n}=1-\left(\genfrac{}{}{0ex}{}{2n}{1}\right)\sqrt[]{2}+\left(\genfrac{}{}{0ex}{}{2n}{2}\right){\sqrt[]{2}}^2-\left(\genfrac{}{}{0ex}{}{2n}{3}\right){\sqrt[]{2}}^3+\text{...}+\left(\genfrac{}{}{0ex}{}{2n}{2k}\right){\sqrt[]{2}}^{2k}-\left(\genfrac{}{}{0ex}{}{2n}{2k+1}\right){\sqrt[]{2}}^{2k+1}+\text{...}+{\sqrt[]{2}}^{2n}\mathrm{.}}\end{array}$ Ha a fenti két kifejezést kivonjuk egymásból, azok a tagok, ahol $\sqrt[]{2}$ páros kitevővel szerepel, kiesnek, azaz $\begin{array}{c}{\displaystyle {\left(1+\sqrt[]{2}\right)}^{2n}-{\left(1-\sqrt[]{2}\right)}^{2n}=2\sqrt[]{2}\left[\left(\genfrac{}{}{0ex}{}{2n}{1}\right)+\left(\genfrac{}{}{0ex}{}{2n}{3}\right){\sqrt[]{2}}^2+\text{...}+\left(\genfrac{}{}{0ex}{}{2n}{2k+1}\right){\sqrt[]{2}}^{2k}+\text{...}+\left(\genfrac{}{}{0ex}{}{2n}{2n-1}\right){\sqrt[]{2}}^{2n-2}\right]\mathrm{.}}\end{array}$ Itt a nagy zárójelben $\sqrt[]{2}$ mindig páros kitevővel szerepel, vagyis csupa egész számot kell összeadni. Következésképp $\left[{\left(1+\sqrt[]{2}\right)}^{2n}-{\left(1-\sqrt[]{2}\right)}^{2n}\right]/\sqrt[]{2}$ egész szám, amint bizonyítani akartuk.   Megjegyzések. 1. Mindhárom megoldás gondolatmenetével bebizonyítható az is, hogy $2\left(a_{2n+1}^2+1\right)$ szintén teljes négyzet. Az első két megoldás gondolatmenete alapján $\begin{array}{c}{\displaystyle 2\left(a_{2n+1}^2+1\right)={\left(a_{2n+1}+a_{2n}\right)}^2\mathrm{.}}\end{array}$ 2. A II. megoldás valójában azt adja, hogy a feladat sorozatára $\begin{array}{c}{\displaystyle 2a_n^2-{\left(a_n+a_{n-1}\right)}^2={\left(-1\right)}^n\cdot 2.}\end{array}$ $a_n^2$-tel osztva és a bal oldalt tényezőkre bontva kapjuk, hogy $\begin{array}{c}{\displaystyle \left(\sqrt[]{2}-\frac{a_n+a_{n-1}}{a_n}\right)\left(\sqrt[]{2}+\frac{a_n+a_{n-1}}{a_n}\right)=\frac{2\cdot {\left(-1\right)}^n}{a_n^2};}\end{array}$ Nyilvánvaló, hogy $\frac{a_n+a_{n-1}}{a_n}>1>2-\sqrt[]{2}$, ezt a második zárójelbe beírva átosztás után adódik, hogy $\begin{array}{c}{\displaystyle |\sqrt[]{2}-\frac{a_n+a_{n-1}}{a_n}|<\frac{1}{a_n^2}\mathrm{.}}\end{array}$ Az $a_n$ nevezőjű $\left(a_n+a_{n-1}\right)/a_n$ tört tehát $1/a_n^2$-nél közelebb van $\sqrt[]{2}$-höz: Ez jó közelítésnek számít, hiszen ha $q$ egész, akkor a $\frac{q}{q}$, $\frac{q+1}{q}$, ... , $\frac{2q}{q}$ alakú törtek közül $\sqrt[]{2}$-höz legközelebbiről általában csak annyit mondhatunk, hogy legföljebb$\frac{1}{2q}$ távolságra van $\sqrt[]{2}$-től. Minthogy $a_n$ nagyon gyorsan nő és tart a végtelenbe, nagy $n$-ekre a fenti becslés a "legjobb'' $a_n$ nevezőjű törtről, azaz $\left(a_n+a_{n-1}\right)/a_n$-ről lényegesen erősebbet állít. Másrészt könnyen bebizonyítható, hogy a "legjobb'' $q$ nevezőjű tört ($q$ egész) is mindig legalább $\frac{1}{3q^2}$ távolságra van $\sqrt[]{2}$-től.