\hfill \hfill } %} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \input{tcilatex} \geometry{left=0.4in,right=0.5in,top=0.5in,bottom=0.4in} \pagestyle{fancy} \lhead{\color{blue} \Large Lecture Notes} \lfoot{\small \copyright $\;$ copyright Hidegkuti, 2014} \cfoot{} \chead{\LARGE Sequences - Part 3} \rfoot{\small Last revised: March 16, 2014} \rhead{\large page \thepage } \textwidth 7.5in \textheight 9.7in \setlength{\headheight}{26pt} \setlength{\parindent}{0pt} \begin{document} \begin{center} {\LARGE Sequences Defined Recursively\bigskip }\bigskip \end{center} %TCIMACRO{% %\TeXButton{box start - 7.5in}{\begin{boxedminipage}{7.5in} %\setlength{\fboxrule}{15pt} %\setlength{\fboxsep}{15pt}}}% %BeginExpansion \begin{boxedminipage}{7.5in} \setlength{\fboxrule}{15pt} \setlength{\fboxsep}{15pt}% %EndExpansion %TCIMACRO{\TeXButton{white}{\color{white}}}% %BeginExpansion \color{white}% %EndExpansion .% %TCIMACRO{\TeXButton{black}{\color{black}}}% %BeginExpansion \color{black}% %EndExpansion Definition: The sequence $\left\{ a_{n}\right\} $ \textbf{converges} to the number $L$ if for every positive number $\varepsilon $ there exists \qquad an integer $N$ such that for all $n$, \begin{equation*} \text{if }n>N\text{ then }\left\vert a_{n}-L\right\vert <\varepsilon \text{.} \end{equation*} \qquad If no such number $L$ exists, we say $\left\{ a_{n}\right\} $ \textbf{% diverges}. \ \qquad If $\left\{ a_{n}\right\} $ converges to $L,$ we write $% \lim\limits_{n\rightarrow \infty }a_{n}=L$ or $a_{n}\rightarrow L$ and call $% L$ the \textbf{limit} of the sequence.\medskip %TCIMACRO{\TeXButton{end of box}{\end{boxedminipage}}}% %BeginExpansion \end{boxedminipage}% %EndExpansion \bigskip Some sequences are defined \textbf{recursively}. \ Recursive definitions enable us to compute the first, second, third, ... $n$th term, but we cannot compute the nth term without first computing the first $n-1$. \ The \textbf{Fibonacci sequence} is a perfect example for this.\bigskip %TCIMACRO{% %\TeXButton{box start - 7.5in}{\begin{boxedminipage}{7.5in} %\setlength{\fboxrule}{20pt} %\setlength{\fboxsep}{20pt}}}% %BeginExpansion \begin{boxedminipage}{7.5in} \setlength{\fboxrule}{20pt} \setlength{\fboxsep}{20pt}% %EndExpansion %TCIMACRO{\TeXButton{white}{\color{white}}}% %BeginExpansion \color{white}% %EndExpansion .% %TCIMACRO{\TeXButton{black}{\color{black}}}% %BeginExpansion \color{black}% %EndExpansion Definition: \ The \textbf{Fibonacci sequence} is defined recursively as \begin{equation*} F_{1}=1,~~F_{2}=1,~~\text{and for all }n\in %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion ,~~~F_{n+2}=F_{n}+F_{n+1} \end{equation*} %TCIMACRO{\TeXButton{end of box}{\end{boxedminipage}}}% %BeginExpansion \end{boxedminipage}% %EndExpansion \medskip \qquad The first few terms of the Fibonacci Sequence are $% 1,1,2,3,5,8,13,21,34,55,89,...$ The explicit formula for the nth term of this sequence is a very interesting formula.\bigskip The following method can be used to find the limit of a recursive sequence - provided that we have already established that the limit exists.\bigskip Example 1. \ Consider the sequence defined recursively: \ $a_{1}=2$ and $% a_{n+1}=\dfrac{1}{2}a_{n}+3$. \ Assume that this limit exists and find its value.\bigskip Solution: \ This method is based on the fact that $\lim\limits_{n\rightarrow \infty }a_{n}=\lim\limits_{n\rightarrow \infty }a_{n+1}$. \ Let us denote this limit by $x$.% \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }a_{n+1} \\ \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }\left( \dfrac{1}{2}a_{n}+3\right) \end{eqnarray*}% Using properties of limits, we re-write the right-hand side: \ \begin{equation*} \lim\limits_{n\rightarrow \infty }\left( \dfrac{1}{2}a_{n}+3\right) =\lim\limits_{n\rightarrow \infty }\left( \dfrac{1}{2}a_{n}\right) +\lim\limits_{n\rightarrow \infty }3=\dfrac{1}{2}\lim\limits_{n\rightarrow \infty }a_{n}+3 \end{equation*}% So now we have:% \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }a_{n} &=&\dfrac{1}{2}\lim\limits_{n% \rightarrow \infty }a_{n}+3 \\ x &=&\dfrac{1}{2}x+3\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ subtract }\dfrac{1}{2}x \\ \dfrac{1}{2}x &=&3\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ multiply by }2 \\ x &=&6 \end{eqnarray*}% So this limit is $6$. \bigskip \pagebreak Example 2. \ Consider the sequence defined recursively: \ $a_{1}=0$, \ $% a_{2}=1$, and $a_{n+1}=a_{n}+2a_{n-1}$. \ Assume that the limit $% \lim\limits_{n\rightarrow \infty }\dfrac{a_{n+1}}{a_{n}}$ exists and find its value.\bigskip Solution: \ \ This method is based on the fact that $\lim\limits_{n% \rightarrow \infty }\dfrac{a_{n+1}}{a_{n}}=\lim\limits_{n\rightarrow \infty }% \dfrac{a_{n}}{a_{n-1}}$. \ Let us denote this limit by $x$.% \begin{equation*} \lim\limits_{n\rightarrow \infty }\dfrac{a_{n+1}}{a_{n}}=\lim\limits_{n% \rightarrow \infty }\dfrac{a_{n}+2a_{n-1}}{a_{n}}=\lim\limits_{n\rightarrow \infty }\dfrac{a_{n}}{a_{n}}+\lim\limits_{n\rightarrow \infty }\dfrac{% 2a_{n-1}}{a_{n}}=1+2\lim\limits_{n\rightarrow \infty }\dfrac{a_{n-1}}{a_{n}} \end{equation*}% \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }\dfrac{a_{n+1}}{a_{n}} &=&1+2\lim% \limits_{n\rightarrow \infty }\dfrac{a_{n-1}}{a_{n}} \\ \lim\limits_{n\rightarrow \infty }\dfrac{a_{n+1}}{a_{n}} &=&1+\dfrac{2}{% \lim\limits_{n\rightarrow \infty }\dfrac{a_{n}}{a_{n-1}}} \\ x &=&1+\dfrac{2}{x}\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ multiply by }x \\ x^{2} &=&x+2 \\ x^{2}-x-2 &=&0 \\ \left( x-2\right) \left( x+1\right) &=&0~~~~~~\Longrightarrow ~~~~~~x_{1}=2% \text{ \ \ }x_{2}=-1 \end{eqnarray*}% since all terms of \ this sequence are positive, the limit is the positive solution, $x=2$.\bigskip \bigskip Example 3. \ Consider the sequence $a_{1}=1$ and $a_{n+1}=\dfrac{1}{2}\left( a_{n}+\dfrac{2}{a_{n}}\right) $. \ Assume that the limit $% \lim\limits_{n\rightarrow \infty }a_{n}$ exists and find its value.\bigskip Solution: \ \ This method is based on the fact that $\lim\limits_{n% \rightarrow \infty }a_{n}=\lim\limits_{n\rightarrow \infty }a_{n+1}$. \ Let us denote this limit by $x$.% \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }a_{n+1} \\ \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }\left( \dfrac{1}{2}\left( a_{n}+\dfrac{2}{a_{n}}\right) \right) \\ \lim\limits_{n\rightarrow \infty }a_{n} &=&\dfrac{1}{2}\lim\limits_{n% \rightarrow \infty }\left( a_{n}+\dfrac{2}{a_{n}}\right) \\ \lim\limits_{n\rightarrow \infty }a_{n} &=&\dfrac{1}{2}\left( \lim\limits_{n\rightarrow \infty }a_{n}+\dfrac{2}{\lim\limits_{n\rightarrow \infty }a_{n}}\right) \\ x &=&\dfrac{1}{2}\left( x+\dfrac{2}{x}\right) \\ x &=&\dfrac{1}{2}x+\dfrac{1}{x}\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ subtract }\dfrac{1}{2}x \\ \dfrac{1}{2}x &=&\dfrac{1}{x}\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ multiply by }x \\ \dfrac{1}{2}x^{2} &=&1\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ multiply by }2 \\ x^{2} &=&2 \\ x &=&\pm \sqrt{2} \end{eqnarray*}% Since all terms of the sequence are positive, the negative solution is ruled out and the limit must be $\sqrt{2}$.\pagebreak Example 4. \ Consider the sequence $a_{1}=5$ and $a_{n+1}=\dfrac{a_{n}+3}{% a_{n}+1}$. \ Assume that the limit $\lim\limits_{n\rightarrow \infty }a_{n}$ exists and find its value.\bigskip Solution: \ \ This method is based on the fact that $\lim\limits_{n% \rightarrow \infty }a_{n}=\lim\limits_{n\rightarrow \infty }a_{n+1}$. \ Let us denote this limit by $x$.% \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }a_{n+1} \\ \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }% \dfrac{a_{n}+3}{a_{n}+1} \\ \lim\limits_{n\rightarrow \infty }a_{n} &=&\dfrac{\lim\limits_{n\rightarrow \infty }a_{n}+3}{\lim\limits_{n\rightarrow \infty }a_{n}+1} \\ x &=&\dfrac{x+3}{x+1}\text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ multiply by }x+1 \\ x\left( x+1\right) &=&x+3 \\ x^{2}+x &=&x+3 \\ x^{2} &=&3 \\ x &=&\pm \sqrt{3} \end{eqnarray*}% Since all terms of the sequence are positive, the negative solution is ruled out and the limit must be $\sqrt{3}$.\bigskip Example 5. \ Compute the value of $\sqrt{20+\sqrt{20+\sqrt{20+...}}}$\bigskip Solution: \ Define $a_{1}=20$ and $a_{n+1}=\sqrt{20+a_{n}}$. \ Assuming the limit exists, $\lim\limits_{n\rightarrow \infty }a_{n}=\lim\limits_{n\rightarrow \infty }a_{n+1}$. \ Let us denote this limit by $x$.% \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }a_{n+1} \\ \lim\limits_{n\rightarrow \infty }a_{n} &=&\lim\limits_{n\rightarrow \infty }% \sqrt{20+a_{n}} \end{eqnarray*}% We will use a theorem here we did not yet prove: that $\lim\limits_{n% \rightarrow \infty }\sqrt{c_{n}}=\sqrt{\lim\limits_{n\rightarrow \infty }c_{n}}$. \ Let us assume this property for now. \ Using properties of limits, \begin{equation*} \lim\limits_{n\rightarrow \infty }\sqrt{20+a_{n}}=\sqrt{\lim\limits_{n% \rightarrow \infty }\left( 20+a_{n}\right) }=\sqrt{\lim\limits_{n\rightarrow \infty }20+\lim\limits_{n\rightarrow \infty }a_{n}}=\sqrt{% 20+\lim\limits_{n\rightarrow \infty }a_{n}} \end{equation*}% So now we have that% \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }a_{n} &=&\sqrt{20+\lim\limits_{n% \rightarrow \infty }a_{n}} \\ x &=&\sqrt{20+x} \\ x^{2} &=&x+20 \\ x^{2}-x-20 &=&0 \\ \left( x-5\right) \left( x+4\right) &=&0~~~~~\Longrightarrow ~~~~~~~x_{1}=5~~~~x_{2}=-4 \end{eqnarray*}% Since all terms of the sequence are positive, the negative solution is ruled out and the limit must be $5$. \pagebreak Example 6. \ Let $F_{1}$, $F_{2}$, $F_{3}$, ... be the Fibonacci sequence defined by $F_{1}=1,~~F_{2}=1,~~$and for$~~F_{n+2}=F_{n}+F_{n+1}$ for $n\geq 1$. \ Compute $\lim\limits_{n\rightarrow \infty }\dfrac{F_{n+1}}{F_{n}}$% .\bigskip Solution: \ Let us denote $\lim\limits_{n\rightarrow \infty }\dfrac{F_{n+1}}{% F_{n}}$ by $x$. \ We will state that $\lim\limits_{n\rightarrow \infty }% \dfrac{F_{n+1}}{F_{n}}=\lim\limits_{n\rightarrow \infty }\dfrac{F_{n+2}}{% F_{n+1}}$ and solve for $x$. \begin{eqnarray*} \lim\limits_{n\rightarrow \infty }\dfrac{F_{n+1}}{F_{n}} &=&\lim\limits_{n% \rightarrow \infty }\dfrac{F_{n+2}}{F_{n+1}} \\ \lim\limits_{n\rightarrow \infty }\dfrac{F_{n+1}}{F_{n}} &=&\lim\limits_{n% \rightarrow \infty }\dfrac{F_{n}+F_{n+1}}{F_{n+1}} \\ \lim\limits_{n\rightarrow \infty }\dfrac{F_{n+1}}{F_{n}} &=&\lim\limits_{n% \rightarrow \infty }\left( \dfrac{F_{n}}{F_{n+1}}+\dfrac{F_{n+1}}{F_{n+1}}% \right) \\ \lim\limits_{n\rightarrow \infty }\dfrac{F_{n+1}}{F_{n}} &=&\lim\limits_{n% \rightarrow \infty }\dfrac{F_{n}}{F_{n+1}}+1 \\ x &=&\dfrac{1}{x}+1 \\ x^{2} &=&1+x \\ x^{2}-x-1 &=&0 \end{eqnarray*}% \begin{equation*} x_{1,2}=\dfrac{1\pm \sqrt{1-\left( -4\right) }}{2}=\dfrac{1\pm \sqrt{5}}{2} \end{equation*}% Since all terms of the sequence are positive, the negative solution, $\dfrac{% 1-\sqrt{5}}{2}$ is ruled out and so the limit must be $\dfrac{1+\sqrt{5}}{2}$% .\bigskip \begin{center} {\LARGE Practice Problems\bigskip } \end{center} Assume that the following sequences all have limits. \ In case of each of the sequences given, find the value of its limit.\bigskip\ \begin{enumerate} \item %TCIMACRO{\TeXButton{2col begin}{\begin{multicols}{2}}}% %BeginExpansion \begin{multicols}{2}% %EndExpansion $a_{1}=2$, \ $a_{n+1}=\dfrac{12}{1+a_{n}}$ \item $a_{1}=-1$, \ \ $a_{n+1}=\dfrac{a_{n}+25}{a_{n}+1}$ \item $a_{1}=-1$, \ \ \ \ $a_{n+1}=\sqrt{5+2a_{n}}$ \item $a_{1}=2$, \ \ \ \ $a_{n+1}=\sqrt{2a_{n}}$ \item $a_{1}=3$, \ \ $a_{n+1}=6-\sqrt{a_{n}}$ \item $a_{1}=10$,\ \ \ $a_{n+1}=4+\dfrac{21}{a_{n}}$ \item $a_{1}=2$, \ $a_{n+1}=\dfrac{1}{2+a_{n}}$ \item $a_{1}=1$, \ $a_{n+1}=\sqrt{1+a_{n}}$ \ %TCIMACRO{\TeXButton{multicol end}{\end{multicols}}}% %BeginExpansion \end{multicols}% %EndExpansion \item Consider the sequence defined recursively as $a_{1}=1$, \ $a_{2}=1$, \ \ $a_{n+2}=2a_{n}+a_{n+1}$. \ Compute $\lim\limits_{n\rightarrow \infty }% \dfrac{a_{n+1}}{a_{n}}$. \item Compute the value of the infinite continued fraction \ $\dfrac{1}{2+% \dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2+...}}}}$ \item A farmer plants A acres of wheat one year. Each year thereafter, he harvests (removes) \ $\dfrac{1}{4}$ of the planted acreage and then plants $% 1500$ more acres. The number of acres of wheat planted approaches what number?\pagebreak \end{enumerate} \bigskip \begin{center} {\LARGE Answers - Practice Problems\bigskip } \end{center} 1.) \ $3$ \ \ \ 2.) \ $5$ \ \ \ \ \ 3.) \ $\sqrt{6}+1$ \ \ \ \ \ 4.) \ $2$ \ \ \ \ \ 5.) \ $4$ \ \ \ \ \ 6.) \ $7$ \ \ \ \ 7.) \ $\sqrt{2}-1$ \ \ \ \ 8.) \ $\dfrac{\sqrt{5}+1}{2}$ \bigskip 9.) $\ 2$ \ \ \ \ \ 10.) \ $\sqrt{2}-1$ \ \ \ \ 11.) \ $6000$ acres \bigskip \medskip \vspace{1.5in}\medskip \medskip \medskip \vspace{6in}\medskip \medskip \medskip {\small %TCIMACRO{\TeXButton{\small}{\small}}% %BeginExpansion \small% %EndExpansion } \href{https://teaching.martahidegkuti.com/shared/lnotes/lecturenotes.html}{% For more documents like this, visit our page at\ https://teaching.martahidegkuti.com and click on Lecture Notes. \ E-mail questions or comments to mhidegkuti@ccc.edu.} \end{document}