\documentclass{article}

%\usepackage{teaching}

\title{Mathematical Methods: Tutorial sheet 8}

\date{1 December 2005}

\author{Peter Harrison}


\renewcommand{\baselinestretch}{1}   % {1,1.25,1.667} = % single/1.5/double line spacing

\newcommand{\answerblock}[1]{{\bf Solutions:}\nopagebreak[1]#1}
\usepackage{mathchars}

\newcommand{\nat}{\bbbn}
\newcommand{\rat}{\bbbq}
\newcommand{\real}{\bbbr}
\newcommand{\integers}{\bbbz}

\renewcommand{\rat}{Q \!\!\!\! O}
\renewcommand{\integers}{Z \!\!\! Z}

%\renewcommand{\answerblock}[1]{}
\newcommand{\bcomment}[1]{}

\newcommand{\mtx}[4]{\left(\begin{array}{rr}#1&#2\\#3&#4\end{array}\right)}
\newcommand{\cmtx}[4]{\left(\begin{array}{cc}#1&#2\\#3&#4\end{array}\right)}
\newcommand{\Bmtx}[9]{\left(\begin{array}{rrr}#1&#2&#3\\#4&#5&#6\\#7&#8&#9\end{array}\right)}
\newcommand{\Bcmtx}[9]{\left(\begin{array}{ccc}#1&#2&#3\\#4&#5&#6\\#7&#8&#9\end{array}\right)}
\newcommand{\vcr}[2]{\left(\begin{array}{r}#1\\#2\end{array}\right)}
\newcommand{\cvcr}[2]{\left(\begin{array}{c}#1\\#2\end{array}\right)}
\newcommand{\Bvcr}[3]{\left(\begin{array}{r}#1\\#2\\#3\end{array}\right)}
\newcommand{\Bcvcr}[3]{\left(\begin{array}{c}#1\\#2\\#3\end{array}\right)}
\newcommand{\zeromtx}{\left(\begin{array}{rr}0&0\\0&0\end{array}\right)}
\newcommand{\identitymtx}{\left(\begin{array}{rr}1&0\\0&1\end{array}\right)}
\newcommand{\determinant}[1]{\left| #1 \right|}

\newcommand{\vi}{\vec{i}}
\newcommand{\vj}{\vec{j}}
\newcommand{\vk}{\vec{k}}


\begin{document}
\maketitle
\noindent {\bf All questions are unassessed, but very useful!.}

\bigskip

{\bf Fixpoints and continuity}
\begin{enumerate}

\item

Consider the quadratic equation $$x^2-2x-1=0$$ which has roots $1\pm \sqrt{2}$.  [Usually in `real' problems
we don't know the answer, but will know a valid range of values, e.g. in the interval [2,3].]  The aim of
this exercise is to compute $\sqrt{2}$ iteratively.  Define the recurrence:
$$a_{n+1} = \sqrt{2a_n+1},\;\;a_1=1$$

\begin{enumerate}
\item Show that, if the recurrence converges, its limit is one of the roots of the quadratic equation above;
\item Prove by induction (if you know how) that $0 < a_n < 3$ for all $n \in \nat$ [if you don't know
induction, just show that $0 < a_n < 3 \Rightarrow 0 < a_{n+1} < 3$];
\item Hence show that if the iteration converges, its limit is the positive root, $l=1+\sqrt{2}$;
\item Calculate $a_{n+1}^2-l^2 = (a_{n+1}+l)(a_{n+1}-l)$ and show that
$$a_{n+1}-l=\frac{2(a_n-l)}{a_{n+1}+l}$$
\item Hence show that $a_n \rightarrow l$ as $n \rightarrow \infty$;
\item Compute $\{ a_n-1 \mid 1\leq n \leq 6 \}$ and compare with $\sqrt{2}$.
\end{enumerate}

\answerblock{
\begin{enumerate}
\item If it converges, then in the limit we can set $a_n = a_{n+1} = l$  (no need for an $\epsilon$-argument
here, although to be strictly rigorous it can be done easily).  Thus $l = \sqrt{2l+1}$ and squaring gives $l^2
= 2l+1$ which is the given quadratic.
\item $a_1=1$ and so $0<a_1<3$ is true.  Suppose $0<a_n<3$ holds for $n \geq 1$.  
Then $$\sqrt{2\times 0 +1} \leq a_{n+1} \leq \sqrt{2\times 3 +1} = \sqrt{7} $$
Thus  certainly $0 \leq a_{n+1} \leq 3$.  Actually, we have all $a_n > 1$.
\item {\em If} the iteration converges, its limit must be $\geq 0$ because every $a_n \geq 0$.  (Again, from
first principles, you would say every large enough $n$ is maximum $\epsilon$ away from the limit, so the
limit can't be less than 0 ...... but you don't need to say this unless it's {\em specfically asked for}.) 
This excludes the negative root $1-\sqrt{2}$.
\item By definition of the recurrence and because $l^2 = 2l+1$, 
$$a_{n+1}^2-l^2 = (\sqrt{2a_n+1})^2 - 2l -1 = 2(a_n-l)$$
Hence, $$(a_{n+1}+l)(a_{n+1}-l) = 2(a_n-l)$$
\item Since $a_{n+1}>0$ and the positive root $l > 2.4$ (because $\sqrt{2} > 1.4$), 
$$a_{n+1}-l < \frac{2}{2.4}(a_n-l)$$ and so $a_{n+1}-l$ converges to 0 by the ratio test.
Thus $a_n \rightarrow l$ as $n \rightarrow \infty$.
\item $a_1 = 1, a_2 = \sqrt{2+1} = \sqrt{3} = 1.732051, a_3 =  \sqrt{2\sqrt{3}+1} = 2.11284, 
a_4 = \sqrt{2\times 2.11284+1} = 2.28598, a_5 = 2.36050, a_6 = 2.39186$ so the set is
$$\{0, 1.732051, 1.11284, 1.28598, 1.36050, 1..39186\}$$ and the next 5 elements are:
$$\{1.40494, 1.41037,
1.41262, 1.41355, 1.41394
\}$$
\end{enumerate}
}


\item Given real functions $g,f$ which are continuous on 
$(a,b)$ and on the image of $g$, $\{z=g(x) \mid x \in (a,b) \}$, respectively, prove rigorously that the
function
$h$ defined by $h(x) = f(g(x))$ is continuous on $(a,b)$.  

{\bf\it Hint}: You have to prove that, given a point $x_0 \in (a,b)$,  $\forall \epsilon>0, \exists \delta>0$
s.t. 
$|x-x_0|<\delta \Rightarrow |h(x)-h(x_0)|<\epsilon$ and find $\delta$ as a function of $\epsilon$, using
corresponding quantities $\delta_f, \delta_g$ relating to the continuity of $f,g$.

\answerblock{
For $h$ to be continuous, as $x$ get very close to $x_0$, then $h(x)$ must get very close to
$h(x_0)$ -- this is what the hint says in a rigorous way.  

Given a point $x_0 \in (a,b)$ and a real
number  $\epsilon>0, \exists \delta_f>0$ s.t. 
$$|g(x)-g(x_0)|<\delta_f \Rightarrow
|f(g(x))-f(g(x_0))|<\epsilon$$ since $f$ is continuous at $g(x_0)$.

But $\exists \delta_g>0$ s.t.  $|x-x_0|<\delta_g \Rightarrow
|g(x)-g(x_0)|<\delta_f$ since $g$ is continuous at $x_0$.  So if we choose $\delta \leq \delta_g$, we have
$$|x-x_0|<\delta \Rightarrow |g(x)-g(x_0)|<\delta_f \Rightarrow|h(x)-h(x_0)|<\epsilon$$ as required.

}




\item  
{\bf Refer to question 3 on Logic Exercises 7 (no. 6 on cate).} 
\newline Let $L$ be the signature consisting of constant-symbols written as the underlined decimal numbers (hence including the positive integer-symbols $\underline{1}, \underline{2}, \underline{3}, \ldots $), binary relation symbols $<, >, \leq, \geq$ and binary function symbols $+, \times$. Let $N$ be the structure whose domain consists of the real numbers $\real$, with the symbols of $L$ interpreted in the natural way.  The formula $\exists v(x=v \times v)$ expresses that $x$ is non-negative, for example. 

\begin{enumerate}
\item In the same kind of way, write down a first-order $L$-formula expressing that the sequence of real numbers $a_1, a_2, \ldots $ converges to a real number as $n$ tends to infinity.
\item Try to express the same statement in the same signature in a different way.
\item Using the rules for negating quantified expressions in predicate logic, define the condition for a sequence $a_1, a_2, \ldots $ {\em not} to converge -- i.e. find the negation of the usual definition of convergence.  What does this condition mean in terms of the existence (or otherwise) of  `tramlines'?
\end{enumerate}

\answerblock{
\begin{enumerate}
\item $\exists l( \forall \epsilon(\exists N(\forall n(n>N \rightarrow (a_n - l) \times (a_n - l) < \epsilon \times \epsilon))))$.
\item Is there a different way?
\item $\forall l( \exists \epsilon(\forall N(\exists n(\neg(n>N \rightarrow (a_n - l) \times (a_n - l) < \epsilon \times \epsilon))))) =  $ 

$\forall l( \exists \epsilon(\forall N(\exists n( n>N \wedge \neg((a_n - l) \times (a_n - l) < \epsilon \times \epsilon)))))$

So for every real number $l$, there is a number  $\epsilon$ for which there are infinitely many $a_n$ lying outside the tramlines  at $l \pm \epsilon$ --- there is no `last' such $a_n$.
\end{enumerate}

}

\end{enumerate}

\end{document}