A snáď občas spomeniem aj nejaké veci, ktoré sa naučíme počas tohoto semestra.
Fibonacciho čísla
Fibonacciho čísla sú definované podmienkou
$$F_{n+2}=F_{n+1}+F_n\tag{1}$$
a počiatočnými podmienkami $F_0=0$, $F_1=1$.
Prvých niekoľko hodnôt je
$$
\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\hline
F_n & 0 & 1 & 1 & 2 & 3 & 5 & 8 &13 &21 \\\hline
\end{array}
$$
Binetov vzorec
Indukciou sa dá overiť, že platí
$$F_n=\frac{a^n-b^n}{a-b}=\frac{\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1+\sqrt5}2\right)^n}{\sqrt5}$$
kde $a=\frac{1+\sqrt5}2$ a $b=\frac{1-\sqrt5}2$ sú korene polynómu $x^2-x-1=0$.
(Môže byť užitočné všimnúť si, že $a+b=1$ a $ab=-1$.)
Teda čísla $a$, $b$ sú vlastne zlatý rez a jeho prevrátená hodnota.
Ukážeme si aj odvodenie pomocou matíc.
Maticové vyjadrenie Fibonacciho čísel
Označme
$A=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}$
Priamo roznásobením vidíme, že platí:
$$
\begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix}=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}
\tag{2}
$$
(Táto maticová rovnosť je vlastne prepísanie rekurencie definujúcej Fibonacciho čísla.)
Podobne môžeme vcelku ľahko overiť, že
$$
\begin{pmatrix}
F_{n+2} & F_{n+1} \\
F_{n+1} & F_{n}
\end{pmatrix}=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{pmatrix}
$$
Keď si ešte všimneme, že
$$A=\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}=
\begin{pmatrix}
F_{2} & F_{1} \\
F_{1} & F_{0}
\end{pmatrix}
$$
tak indukciou vieme vcelku ľahko dokázať, že platí
$$A^n=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n=
\begin{pmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{pmatrix}\tag{3}
$$
Práve tento vzťah sa budeme snažiť použiť na odvodenie viacerých vlastností Fibonacciho postupnosti.
Môžete sa skúsiť zamyslieť aj nad tým, či by ste ich vedeli odvodiť nejako inak, napríklad:
- priamo z Binetovho vzorca;
- použitím indukcie;
- použitím generujúcich funkcií a.k.a. vytvárajúcich funkcií;
- použitím kombinatorického významu Fibonacciho čísel
Ak vás bavia kombinatorické dôkazy, tak veľa dôkazov identít s Fibonacciho číslami sa dá nájsť v knihe Benjamin, Arthur T.; Quinn, Jennifer J.: Proofs That Really Count: The Art of Combinatorial Proof. (V prípade záujmu môžem poskytnúť.)
Pre niektoré z identít, ktoré uvedieme, by bol možno iný dôkaz jednoduchší alebo porovnateľne náročný. Pre niektoré je asi najjednoduchší postup pomocou matíc.
Charakteristický polynóm matice $A$
Pretože táto vlastnosť môže byť pre nás užitočná pri niektorých výpočtoch, môžeme si všimnúť, že
$$A^2=A+I.$$
To môžeme overiť priamym výpočtom
$\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^2=
\begin{pmatrix}
2 & 1 \\
1 & 1
\end{pmatrix}=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
+
\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}$
Platnosť tejto rovnosti však vieme aj z Cayley-Hamiltonovej vety. Stačí nájsť charakteristický polynóm matice $A$
$|xI-A|=
\begin{vmatrix}
x-1 & -1 \\
-1 & x
\end{vmatrix}=x(x-1)-1=x^2-x-1$.