\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

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

\pagestyle{empty}

\begin{center}
{\sc \Large Ułamki łańcuchowe}
\end{center}

\noindent
Ułamek $\frac{253}{48}$ zapisujemy w postaci ułamka łańcuchowego następująco:
{\footnotesize\formula{
 \frac{253}{48}
 = 5 + \cfrac{13}{48}
 = 5 + \cfrac{1}{\frac{48}{13}}
 = 5 + \cfrac{1}{3 + \cfrac{9}{13}}
 = 5 + \cfrac{1}{3 + \cfrac{1}{\frac{13}{9}}}
 = 5 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{4}{9}}}
 = 5 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{\frac{9}{4}}}}
 = 5 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{4}}}} \, .
}}
\vspace*{-2em}\par\noindent
W skrócie pisze się:
\formula{
 \sfrac{254}{48} = [\sfrac{254}{48}] = [5 + \sfrac{13}{48}] = [5; \sfrac{48}{13}] = [5; 3 + \sfrac{9}{13}] = [5; 3, \sfrac{13}{9}] = [5; 3, 1 + \sfrac{4}{9}] = [5; 3, 1, \sfrac{9}{4}] = [5; 3, 1, 2 + \sfrac{1}{4}] = [5; 3, 1, 2, 4].
}
Zwróć uwagę na średnik w zapisie.
\begin{enumerate}
\setcounter{enumi}{0}
\item Rozwiń w ułamek łańcuchowy liczby $\frac{730}{81}$, $\frac{500}{32}$, $\frac{13}{21}$, $\frac{355}{113}$. Rozwikłaj ułamek łańcuchowy $[0; 5, 10, 15]$.
\item Opisz (rekurencyjną) procedurę rozwijania dodatniej liczby wymiernej w ułamek łańcuchowy i uzasadnij, że procedura ta kończy się w skończonej liczbie kroków.
\item Co się dzieje, gdy w postaci ułamka łańcuchowego spróbujemy zapisać $\sqrt{2}$, $\sqrt{3}$, $\frac{\sqrt{5}+1}{2}$, $\sqrt{5} + 1$?
\item Znajdź liczbę, która rozwijana w postaci ułamka łańcuchowego daje $[4; 1, 4, 1, 4, 1, 4, ...]$. Jaka liczba daje rozwinięcie $[3; 3, 3, 3, ...]$? A jaka $[1; 1, 1, 2, 1, 2, 1, 2, 1, ...]$?
\item Zauważ, że $[a_0; a_1, ..., a_{n-1}, a_n, 1] = [a_0; a_1, ..., a_{n-1}, a_n + 1]$, więc zapis w postaci ułamka łańcuchowego nie jest jednoznaczny. Czy są niejednoznaczności innego rodzaju?
\item Zapisz w postaci ułamka zwykłego ułamek łańcuchowy $[a_0; a_1, a_2, a_3]$.
\item Uzasadnij, że $\ds{ [a_0; a_1, a_2, ..., a_n] = \frac{P_n(a_0, ..., a_n)}{Q_n(a_0, ..., a_n)} }$, gdzie $P_n$ i $Q_n$ spełniają zależność rekurencyjną:
 \formula{
  P_0(x_0) & = x_0 , & P_n(x_0, x_1, ..., x_n) & = x_0 P_{n-1}(x_1, ..., x_n) + Q_{n-1}(x_1, ..., x_n) , \\
  Q_0(x_0) & = 1 , & Q_n(x_0, x_1, ..., x_n) & = P_{n-1}(x_1, ..., x_n) .
 }
\item Udowodnij, że $P_n(x_0, x_1, ..., x_n) = P_n(x_n, x_{n-1}, ..., x_0)$.
\item Niech $x_0, x_1, ...$ będą liczbami rzeczywistymi. Wprowadźmy oznaczenia:
 \formula{
  p_{-1} & = 1, & p_n & = P_n(x_0, x_1, ..., x_n) , \\
  q_{-1} & = 0, & q_n & = Q_n(x_0, x_1, ..., x_n) .
 }
 Udowodnij, że $q_n p_{n-1} - p_n q_{n-1} = (-1)^n$ ($n \ge 0$), czyli innymi słowy (o ile nie dzielimy przez zero):
 \formula{\frac{p_{n-1}}{q_{n-1}} - \frac{p_n}{q_n} & = \frac{(-1)^n}{q_{n-1} q_n} .}
\item Wywnioskuj, że $\mathrm{NWD}(P_n(a_0, a_1, ..., a_n), Q_n(a_0, a_1, ..., a_n)) = 1$ ($a_0, a_1, ..., a_n$ --- liczby całkowite).
\item Uzasadnij, że $[a_0; a_1, ..., a_n, x]$ (gdzie $a_1, a_2, ..., a_n$ są całkowite dodatnie, $a_1$ jest całkowita, $x$ jest rzeczywista dodatnia) jest funkcją rosnącą $x$ gdy $n$ jest nieparzyste oraz funkcją malejącą $x$ w przeciwnym przypadku.
\item Wywnioskuj, że (przy założeniach z poprzedniego zadania oraz $x \ge 1$) liczba $[a_0; a_1, ..., a_n, x]$ leży pomiędzy $[a_0; a_1, ..., a_n]$ oraz $[a_0; a_1, ..., a_n + 1]$ i jest od obu tych liczb oddalona o nie więcej niż $\frac{1}{Q_n(a_0, a_1, ..., a_n)^2}$.
\item Udowodnij, że
 \begin{enumerate}
 \item[(a1)] dla dowolnych liczb całkowitych dodatnich $a_1, a_2, ..., a_n$ i dowolnego $a_0$ całkowitego, liczba $[0; a_1, ..., a_n]$ jest wymierna;
 \item[(a2)] dla dowolnych liczb całkowitych dodatnich $a_1, a_2, ...$ i dowolnego $a_0$ całkowitego, ciąg $[a_0; a_1, ..., a_n]$ jest zbieżny, a jego granica jest liczbą niewymierną;
 \item[(b1)] dla dowolnej liczby wymiernej $x$ istnieją liczby całkowite dodatnie $a_1, a_2, ..., a_n$ i liczba całkowita $a_0$ takie, że $x = [a_0; a_1, ..., a_n]$;
 \item[(b2)] dla dowolnej liczby niewymiernej $x$ istnieją liczby całkowite dodatnie $a_1, a_2, ...$ oraz liczba całkowita $a_0$ takie, że ciąg $[a_0; a_1, ..., a_n]$ dąży do $x$;
 \item[(c1)] ciąg opisany w punkcie (b1) jest dany jednoznacznie, jeśli dodatkowo założymy że $a_n > 1$; w przeciwnym razie istnieją dwa takie ciągi; 
 \item[(c2)] ciąg opisany w punkcie (b2) jest dany jednoznacznie.
 \end{enumerate}
\end{enumerate}

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

\newpage

\noindent
Odpowiedzi i wskazówki:
\begin{enumerate}
\item $\frac{730}{81} = [9; 81]$, $\frac{500}{32} = [15; 1, 1, 1, 2]$, $\frac{13}{21} = [0; 1, 1, 1, 1, 1, 2]$, $\frac{355}{113} = [3; 7, 16]$, $[0; 5, 10, 15] = \frac{151}{770}$.
\item $\frac{n q + r}{q} = n + \frac{1}{q/r}$, czyli $[\frac{n q + r}{q}] = [n; \frac{q}{r}]$. Wskazówka: uzasadnij, że mianownik się zmiejsza.
\item $\sqrt{2} = [1; 2, 2, 2, ...]$, $\sqrt{3} = [1; 1, 2, 1, 2, 1, 2, ...]$, $\frac{\sqrt{5} + 1}{2} = [1; 1, 1, 1, ...]$, $\sqrt{5} + 1 = [3; 4, 4, 4, ...]$.
\item Wskazówka: jeśli $x = [4; 1, 4, 1, 4, 1, 4, ...]$, to $x = 4 + \frac{1}{1 + \frac{1}{x}}$ (lub inaczej $x = [4; 1, x]$); gdy $y = [3; 3, 3, 3, ...]$, to $y = [3, y] = 3 + \frac{1}{y}$; aby wyznaczyć $[1; 1, 1, 2, 1, 2, 1, 2, 1, ...]$, znajdź najpierw $[1; 2, 1, 2, 1, 2, 1, ...]$.
\item Jest to jedyna niejednoznaczność.
\item $\frac{1 + a_0 a_1 + a_0 a_3 + a_2 a_3 + a_0 a_1 a_2 a_3}{a_1 + a_3 + a_1 a_2 a_3}$.
\setcounter{enumi}{7}
\item Wskazówka: indukcja. Rozwiń $P_{n+1}$, skorzystaj z założenia indukcyjnego, rozwiń jeszcze raz $P_n$, skorzystaj z założenia indukcyjnego, zwiń $P_n$, skorzystaj po raz trzeci z założenia indukcyjnego, zwiń $P_{n+1}$.
\setcounter{enumi}{10}
\item Wskazówka: indukcja; $[a_0; a_1, ..., a_{n-1}, a_n, x] = [a_0; a_1, ..., a_{n-1}, a_n + \frac{1}{x}]$.
\item Wskazówka: zastosuj wynik zadania 9. dla ułamka łańcuchowego $[a_0; a_1, ..., a_{n-1}, a_n, 1]$ i wyznacz różnicę między $\frac{p_n}{q_n}$ i $\frac{p_{n+1}}{q_{n+1}}$.
\end{enumerate}

\bigskip

\noindent
Uwagi:
\begin{enumerate}
\item W rozwinięciu w ułamek łańcuchowy $[a_0; a_1, a_2, ..., a_n]$ liczby $a_0, a_1, ..., a_n$ muszą być całkowite, wszystkie oprócz $a_0$ muszą też być dodatnie. Natomiast sama notacja:
\formula{
 [x_0; x_1, x_2, ..., x_n] & = x_0 + \cfrac{1}{x_1 + \cfrac{1}{x_2 + \cfrac{1}{\ddots + \cfrac{1}{x_n}}}}
}
jest zdefiniowana dla dowolnych liczb rzeczywistych $x_0, x_1, ..., x_n$, pod warunkiem, że nigdzie nie występuje dzielenie przez zero.
\setcounter{enumi}{2}
\item Sprawę zbieżności rozwinięcia w ułamek łańcuchowy liczb niewymiernych rozstrzyga ostatnie zadanie.
\item W miarę łatwo można udowodnić, że każda liczba o okresowym rozwinięciu w ułamek łańcuchowy jest \emph{niewymiernością kwadratową}, tj. pierwiastkiem równania kwadratowego. Twierdzenie odwrotne też jest prawdziwe, ale sporo trudniejsze.
\setcounter{enumi}{11}
\item Ciekawy jest wniosek z tego zadania: liczby wymierne $\frac{p_n}{q_n} = [a_0; a_1, ..., a_n]$ są przybliżeniami liczby $x = [a_0; a_1, a_2, ...]$ (o rozwinięciu skończonym lub nie) spełniającymi nierówność $|x - \frac{p_n}{q_n}| < \frac{1}{q_n^2}$. Są to w pewnym sensie najlepsze przybliżenia liczby $x$. Znajdź (posługłując się kalkulatorem) pierwszych kilka wyrazów rozwinięcia w ułamek łańcuchowy liczby $\pi$ i podaj kilka dobrych przylibżeń $\pi$ przez liczby wymierne.
\end{enumerate}

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

\end{document}
