\documentclass[a4paper,10pt]{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[margin=.5in]{geometry}
\usepackage{t1enc}
\usepackage[latin2]{inputenc}
\usepackage[polish]{babel}
\usepackage{ifthen}
\usepackage{color}

\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\expr}[1]{\left( #1 \right)}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\N}{\mathbf{N}}
\newcommand{\Q}{\mathbf{Q}}
\newcommand{\R}{\mathbf{R}}
\newcommand{\Z}{\mathbf{Z}}
\newcommand{\pr}{\mathbf{P}}
\newcommand{\ex}{\mathbf{E}}
\newcommand{\ind}{\mathbf{1}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ph}{\varphi}
\newcommand{\ro}{\varrho}
\newcommand{\thet}{\vartheta}
\newcommand{\sub}{\subseteq}
\newcommand{\cl}[1]{\overline{#1}}
\newcommand{\bd}[1]{\partial #1}
\newcommand{\sfrac}[2]{\mbox{$\frac{#1}{#2}$}}
\newcommand{\ds}{\displaystyle}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\id}{Id}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\tg}{tg}
\DeclareMathOperator{\arctg}{arctg}

\newcommand{\formula}[2][nolabel]
{\ifthenelse{\equal{#1}{nolabel}}
 {\begin{align*} #2 \end{align*}}
 {\ifthenelse{\equal{#1}{}}
  {\begin{align} #2 \end{align}}
  {\begin{align} \label{#1} #2 \end{align}}
 }
}

%
%                            ---------- o ----------
%

\begin{document}
\sloppy

\pagestyle{empty}

\begin{center}\Large\textsc{Liczby Fibonacciego}\end{center}

\newcommand{\otag}[1]{{\footnotesize[#1]}}
%\newcommand{\sol}[1]{{\par\footnotesize\textsc{Rozwiązanie:} #1}}
\newcommand{\sol}[1]{}

\noindent Ciąg liczb Fibonacciego zdefiniowany jest rekurencyjnie wzorami $F_0 = 0$, $F_1 = 1$ oraz $F_n = F_{n-1} + F_{n-2}$ dla $n \ge 2$.

\bigskip

\noindent \textbf{Największy wspólny dzielnik}

\begin{enumerate}
\item Udowodnij, że $F_{n+1} \, F_{n-1} - F_n^2 = (-1)^n$.
\item Udowodnij, że $\mathrm{NWD}(F_n, F_{n+1}) = 1$.
\item Udowodnij, że $F_{k+l} = F_k \, F_{l+1} + F_{k-1} \, F_l$ ($k \ge 1$, $l \ge 0$).
\item Udowodnij, że $\mathrm{NWD}(F_k, F_l) = F_{\mathrm{NWD}(k, l)}$.
\end{enumerate}

\noindent \textbf{Wzór Bineta}

\begin{enumerate}
\item Znajdź ciągi geometryczne $(a_n)$ spełniające równanie $a_n = a_{n-1} + a_{n-2}$.
\item Uzasadnij, że suma dwóch ciągów spełniających równanie $a_n = a_{n-1} + a_{n-2}$ również je spełnia.
\item Znajdź jawny wzór na $F_n$.
\end{enumerate}

\noindent Wzór Bineta jest postaci $F_n = \frac{1}{\sqrt{5}} (\alpha^n - \beta^n)$. W poniższych zadaniach wyniki powinny być wyrażone za pomocą odpowiednich wyrazów ciągu Fibonacciego.

\begin{enumerate}
\item Oblicz $\alpha \cdot \beta$, $\frac{1}{1 - \alpha}$, $\frac{1}{1 - \beta}$, $\frac{1}{1 - \alpha^2}$,  $\frac{1}{1 - \beta^2}$, $\frac{1}{1 - \alpha^3}$,  $\frac{1}{1 - \beta^3}$.
\item Oblicz $F_n^2 + F_{n-1}^2$ oraz $F_{n+1}^2 - F_{n-1}^2$.
\item Oblicz $F_1 + F_2 + ... + F_n$. Zrób to wpierw odgadując odpowiedź i dowodząc jej indukcyjnie, a potem wykorzystując wzór Bineta.
\item Oblicz $F_1^2 + F_2^2 + ... + F_n^2$. Wykorzystaj wzór Bineta i własności $\alpha$ i $\beta$.
\item Oblicz w podobny sposób $F_1^3 + F_2^3 + ... + F_n^3$.
\item Zależność rekurencyjną $F_n = F_{n-1} + F_{n-2}$ można wykorzystać do wyznaczenia $F_n$ dla wszystkich liczb całkowitych $n$ (także ujemnych). Jaki jest związek między $F_{-n}$ i $F_n$ dla $n$ całkowitych?
\end{enumerate}

\noindent{\footnotesize\textsc{Odpowiedzi:} 2. $F_{2n-1}$ i $F_{2n}$; 3. $F_{n+2} - 1$; 4. $F_n F_{n+1}$; 5. $\frac{1}{10}(F_{3n+2} - (-1)^n 6 F_{n-1} + 5)$.}

\begin{flushright}
Mateusz Kwaśnicki
\end{flushright}

%
%                            ---------- o ----------
%

\end{document}
