Feladat:	B.4347	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Kabos Eszter ,  Kúsz Ágnes ,  Lajos Mátyás ,  Lenger Dániel ,  Perjési Gábor ,  Vuchetich Bálint ,  Zilahi Tamás
Füzet:	2012/február, 90. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Fibonacci-sorozat, Négyzetek, Indirekt bizonyítási mód
Hivatkozás(ok):	Feladatok: 2011/március: B.4347

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.   Megoldás. A Fibonacci-számok sorozatát az $F_1=1$, $F_2=1$, $F_n=F_{n-1}+F_{n-2}$ ($n\ge 3$) rekurzióval definiáljuk. Először $n$ szerinti teljes indukcióval igazoljuk az $\begin{array}{c}{\displaystyle F_n^2+F_{n-1}^2+\text{...}+F_2^2+F_1^2=F_n{F}_{n+1}}\end{array}$ összefüggést. Az egyenlőség $n=1$ esetén teljesül, hiszen $1^2=1\cdot 1$, ha pedig valamely $n$-re teljesül az állítás, akkor ${\displaystyle \begin{array}{cc}\hfill {\displaystyle F_{n+1}^2+F_n^2+F_{n-1}^2+\text{...}+F_2^2+F_1^2}& {\displaystyle =F_{n+1}^2+F_n{F}_{n+1}=F_{n+1}\left(F_n+F_{n+1}\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =F_{n+1}{F}_{n+2}}\hfill \end{array}}$ alapján $n+1$ esetén is fennáll. Tegyük fel indirekten, hogy egy téglalapot felbontottunk különböző méretű négyzetekre úgy, hogy minden négyzet oldalhossza Fibonacci-szám. A két legnagyobb négyzet oldalának hossza legyen $F_m$ és $F_n$, ahol $m<n$. Ekkor a téglalap $T$ területére $\begin{array}{c}{\displaystyle T\ge \left(F_m+F_n\right)F_n\mathrm{,}}\end{array}$ mert mindkét oldalának hossza legalább $F_n$, a hosszabb oldalé pedig legalább $F_m+F_n$. Másrészt viszont, mivel a téglalapot fedő négyzetek között nincsenek azonos oldalhosszúságúak, ezért a fenti azonosságot felhasználva a területre a $\begin{array}{c}{\displaystyle T\le F_2^2+F_3^2+\text{...}+F_m^2+F_n^2<F_m{F}_{m+1}+F_n^2}\end{array}$ felső becslést kapjuk. A területre vonatkozó alsó és felső becslést összevetve $\begin{array}{c}{\displaystyle \left(F_m+F_n\right)F_n=F_m{F}_n+F_n^2<F_m{F}_{m+1}+F_n^2}\end{array}$ adódik, amely az $n>m$ feltételnek ellentmondó $F_n<F_{m+1}$ egyenlőtlenséggel ekvivalens. Ebből az ellentmondásból következik, hogy nem lehet minden négyzet oldalhossza Fibonacci-szám.