Problem of the Month
Solution to Problem 0: September 2023

1. 1. 
      

      $$\begin{array}{rl}{r}_2=f(r_1)& =\frac{2r_1-1}{r_1+2}\\ & =\frac{2\left(\frac{3}{2}\right)-1}{\frac{3}{2}+2}\\ & =\frac{4}{7}\end{array}$$ $$\begin{array}{rl}{r}_3=f(r_2)& =\frac{2\left(\frac{4}{7}\right)-1}{\frac{4}{7}+2}\\ & =\frac{1}{18}\end{array}$$ $$\begin{array}{rl}{r}_4=f(r_3)& =\frac{2\left(\frac{1}{18}\right)-1}{\frac{1}{18}+2}\\ & =-\frac{16}{37}\end{array}$$

   2. Observe that $f(r)$ is only undefined when $r=-2$, so to choose $r_1$ so that $r_3=f(r_2)$ is undefined, we need $r_2=-2$. Therefore, $r_2=f(r_1)=-2$, which gives rise to the equation ${\displaystyle \frac{2r_1-1}{r_1+2}}=-2$. Multiplying both sides by $r_1+2$ gives $2r_1-1=-2(r_1+2)$, which can be rearranged to get $4r_1=-3$, so $r_1=-\frac{3}{4}$. Indeed, if $r_1=-\frac{3}{4}$, then $r_2=-2$ and $r_3$ is undefined.

2. 1. $$\begin{array}{rl}{r}_2=f(r_1)& ={\displaystyle \frac{\frac{3}{7}+3}{2\left(\frac{3}{7}\right)-1}}\\ & =-24.\end{array}$$ $$\begin{array}{rl}{r}_3=f(r_2)& =\frac{-24+3}{2(-24)-1}\\ & =\frac{-21}{-49}\\ & =\frac{3}{7}\\ & =r_1\end{array}$$ We have that $r_3=r_1$, so this means $r_4=f(r_3)=f(r_1)=r_2$, and using these facts, $r_5=f(r_4)=f(r_2)=r_3=r_1$. This will continue to get that $r_n=\frac{3}{7}$ when $n$ is odd and $r_n=-24$ when $n$ is even.

   2. First observe that $f(r)$ is undefined only when $2r-1=0$, or $r=\frac{1}{2}$. Therefore, if $r_1=\frac{1}{2}$, then $r_2=f(r_1)$ is undefined.

      Now suppose $f(r)=\frac{1}{2}$. Then ${\displaystyle \frac{r+3}{2r-1}}=\frac{1}{2}$, which can be rearranged to get the equation $2r+6=2r-1$. This equation implies $6=-1$, which is nonsense, and so we conclude that there is no $r$ such that $f(r)=\frac{1}{2}$.

      The only way that the sequence can fail to be defined somewhere is if $r_n=\frac{1}{2}$ for some $n$. This happens if $r_1=\frac{1}{2}$, but since $\frac{1}{2}$ is never the output of $f$, it is not possible that $r_n=\frac{1}{2}$ unless $n=1$. Therefore, $r_1=\frac{1}{2}$ is the only starting value for which the sequence is undefined somewhere.

      Assuming $r\ne \frac{1}{2}$, we will now compute a general expression for $f(f(r))$. Since $r\ne \frac{1}{2}$ and $f(r)\ne \frac{1}{2}$ regardless of $r$, there will be no issues with the expression being undefined. $$\begin{array}{rl}f(f(r))& =\frac{\frac{r+3}{2r-1}+3}{2\left(\frac{r+3}{2r-1}\right)-1}\\ & =\frac{r+3+3(2r-1)}{2(r+3)-(2r-1)}& \text{(multiply through by }2r-1\text{)}\\ & =\frac{7r}{7}\\ & =r\end{array}$$ and so we have that $f(f(r))=r$ for all $r\ne \frac{1}{2}$. We can use this equation to get $r_3=f(r_2)=f(f(r_1))=r_1$. Next, we can compute $r_5=f(r_4)=f(f(r_3))=r_3=r_1$. Continuing, we see that $r_n=r_1$ for all odd $n$. Similarly, $r_4=f(r_3)=f(f(r_2))=r_2$, and we can continue with this reasoning to get that $r_n=f(r_1)=r_2={\displaystyle \frac{r_1+3}{2r_1-1}}$ for all even $n$.

      To answer the given question, since $2023$ is odd, $r_{2023}=r_1$ and since $2024$ is even, $r_{2024}={\displaystyle \frac{r_1+3}{2r_1-1}}$.

3. 1. The values along with their decimal approximations are in the table below.

      Term	Value	Decimal Approximation
      $r_1$	$1$	$1$
      $r_2$	$\frac{3}{2}$	$1.5$
      $r_3$	$\frac{7}{5}$	$1.4$
      $r_4$	$\frac{17}{12}$	$1.416667$
      $r_5$	$\frac{41}{29}$	$1.413793$
      $r_6$	$\frac{99}{70}$	$1.414286$
      $r_7$	$\frac{239}{169}$	$1.414201$
      $r_8$	$\frac{577}{408}$	$1.414216$
      $r_9$	$\frac{1393}{985}$	$1.414213$

   2. We will work with the quantity ${\displaystyle \frac{f(r)-\sqrt{2}}{r-\sqrt{2}}}$ and worry about the absolute value later. $$\begin{array}{rl}\frac{f(r)-\sqrt{2}}{r-\sqrt{2}}& =\frac{\frac{r+2}{r+1}-\sqrt{2}}{r-\sqrt{2}}\\ & =\frac{r+2-\sqrt{2}(r+1)}{(r+1)(r-\sqrt{2})}& \text{(multiply through by }r+1\text{)}\\ & =\frac{r-\sqrt{2}+2-\sqrt{2}r}{(r+1)(r-\sqrt{2})}\\ & =\frac{r-\sqrt{2}-\sqrt{2}(r-\sqrt{2})}{(r+1)(r-\sqrt{2})}\\ & =\frac{(r-\sqrt{2})(1-\sqrt{2})}{(r+1)(r-\sqrt{2})}\\ & =\frac{1-\sqrt{2}}{r+1}& \text{(cancel }r-\sqrt{2}\text{)}\end{array}$$ The result now follows by taking the absolute value of both sides.

   3. Observe that if $r$ is positive, then $f(r)={\displaystyle \frac{r+2}{r+1}}$ is also positive since $r+2$ and $r+1$ are both positive. It follows that if $r_1$ is positive, then $r_n$ is positive for all $n$. Since $r_n>0$ for all $n$, $r_n+1>1$ for all $n$, and taking reciprocals, we get ${\displaystyle \frac{1}{r_n+1}}<1$ for all $n$. Since $r_n+1$ is positive, $\left|{\displaystyle \frac{1}{r_n+1}}\right|={\displaystyle \frac{1}{r_n+1}}$, so we actually get that $\left|{\displaystyle \frac{1}{r_n+1}}\right|<1$ for all $n$.

      We will now show that $|1-\sqrt{2}|<\frac{1}{2}$ (you may already believe this to be true, but the proof presented does not assume that we have a known approximation of $\sqrt{2}$). To see this, observe that $8<9$, and so $\sqrt{8}<\sqrt{9}$ which is the same as $2\sqrt{2}<3$. Dividing both sides by $2$, we get $\sqrt{2}<\frac{3}{2}$. Subtracting $\frac{1}{2}+\sqrt{2}$ from both sides gives $-\frac{1}{2}<1-\sqrt{2}$. Now observe that $1<2$, so $\sqrt{1}<\sqrt{2}$ or $1<\sqrt{2}$. Therefore, $1-\sqrt{2}<0$.

      We have shown that $-\frac{1}{2}<1-\sqrt{2}<0$, which implies that $|1-\sqrt{2}|<\frac{1}{2}$. Combining this with $\left|{\displaystyle \frac{1}{r_n+1}}\right|<1$, we get $$\left|\frac{1-\sqrt{2}}{r_n+1}\right|=\left|\frac{1}{r_n+1}\right||1-\sqrt{2}|<1\times \frac{1}{2}=\frac{1}{2}$$ so $\left|{\displaystyle \frac{1-\sqrt{2}}{r_n+1}}\right|<\frac{1}{2}$.

      Since $r_n=f(r_{n-1})$ for all $n\ge 2$, we can apply part (ii) to get $$\left|\frac{r_n-\sqrt{2}}{r_{n-1}-\sqrt{2}}\right|=\left|\frac{f(r_{n-1})-\sqrt{2}}{r_{n-1}-\sqrt{2}}\right|=\left|\frac{1-\sqrt{2}}{r_{n-1}+1}\right|<\frac{1}{2}$$ where the final inequality comes from applying what we showed above.

      This implies that for all $n\ge 2$ we have $$\begin{array}{}\text{(*)}& |r_n-\sqrt{2}|<\frac{1}{2}|r_{n-1}-\sqrt{2}|\end{array}$$

      Now let’s return to the inequality in the question, which is $|r_n-\sqrt{2}|<{\displaystyle \frac{1}{2^{n-1}}}|r_1-\sqrt{2}|$.

      When $n=2$, this inequality is $|r_2-\sqrt{2}|<\frac{1}{2}|r_1-\sqrt{2}|$, which is exactly $(\ast )$ when $n=2$. We have already shown that $(\ast )$ is true for all $n$, so this means the desired inequality is true for $n=2$.

      When $n=3$, we can apply $(\ast )$ to get $|r_3-\sqrt{2}|<\frac{1}{2}|r_2-\sqrt{2}|$, but we have just shown that $|r_2-\sqrt{2}|<\frac{1}{2}|r_1-\sqrt{2}|$. Therefore, $$|r_3-\sqrt{2}|<\frac{1}{2}|r_2-\sqrt{2}|<\frac{1}{2}(\frac{1}{2}|r_1-\sqrt{2}|)=\frac{1}{2^2}|r_1-\sqrt{2}|$$ which shows that the desired inequality holds for $n=3$.

      By similar reasoning, we can use the fact that the inequality holds for $n=3$ to prove that it holds for $n=4$, then we can use that it holds for $n=4$ to prove that it holds for $n=5$, and so on to show that the inequality holds for all positive integers $n\ge 2$. We can formalize this using mathematical induction.

      Assume that $k\ge 2$ is an integer for which the inequality $|r_k-\sqrt{2}|<{\displaystyle \frac{1}{2^{k-1}}}|r_1-\sqrt{2}|$ is true. Using $(\ast )$ with $n=k+1$, we have the following $$|r_{k+1}-\sqrt{2}|<\frac{1}{2}|r_k-\sqrt{2}|$$ and now using the inductive hypothesis, that $|r_k-\sqrt{2}|<\frac{1}{2^{k-1}}|r_1-\sqrt{2}|$, we get $$|r_{k+1}-\sqrt{2}|<\frac{1}{2}(|r_k-\sqrt{2}|)<\frac{1}{2}(\frac{1}{2^{k-1}}|r_1-\sqrt{2}|)=\frac{1}{2^k}|r_1-\sqrt{2}|$$ but $k=(k+1)-1$, so we have shown that the inequality holds for the integer $k+1$.

      To summarize, we have shown that the inequality holds for $n=2$, and we have shown that if the inequality holds for an integer, then it holds for the next integer. This shows that the inequality holds for all integers $n\ge 2$.

      Finally, since $|r_1-\sqrt{2}|$ is a fixed quantity, the quantity ${\displaystyle \frac{1}{2^{n-1}}}|r_1-\sqrt{2}|$ must get closer and closer to $0$ as $n$ gets larger and larger. We also have that $|r_n-\sqrt{2}|<{\displaystyle \frac{1}{2^{n-1}}}|r_1-\sqrt{2}|$ for all $n$, which means the quantity $|r_n-\sqrt{2}|$, which is positive, is also getting closer and closer to $0$ as $n$ gets larger and larger. It follows that $r_n-\sqrt{2}$ is very close to zero for very large $n$, which means $r_n$ is very close to $\sqrt{2}$ for very large $n$. Keep in mind that this is true for any positive starting value $r_1$.

4. Here is a brief summary of the behaviours of the sequences.

   When $f(r)={\displaystyle \frac{r-3}{r-2}}$, the sequence will repeat with period $3$ as long as at least three terms in the sequence are defined. The only values of $r_1$ for which the sequence has an undefined term are $r_1=2$ and $r_1=1$.

   When $f(r)={\displaystyle \frac{r-1}{5r+3}}$, the sequence will repeat with period $4$ as long as at least four terms are defined. The only values of $r_1$ for which the sequence has an undefined term are $r_1=-\frac{3}{5}$, $r_1=-\frac{1}{5}$, and $r_1=\frac{1}{5}$.

   When $f(r)={\displaystyle \frac{r-1}{r+2}}$, the sequence will repeat with period $6$ as long as at least six terms are defined. The only values of $r_1$ for which the sequence has an undefined term are $r_1=-2$, $r_1=-1$, $r_1=-\frac{1}{2}$, $r_1=0$, and $r_1=1$.

   When $f(r)={\displaystyle \frac{2r+2}{3r+3}}$, the sequence is undefined after $r_1$ if $r_1=-1$. Otherwise, the sequence has $r_n=\frac{2}{3}$ for all $n\ge 2$, regardless of the value of $r_1$.

   Note: These examples, together with the one in part (b), show that the sequences can be periodic with period $1$, $2$, $3$, $4$, or $6$. Do you think that any other periods are possible?

   When $f(r)={\displaystyle \frac{r+1}{r-2}}$, the sequence converges to ${\displaystyle \frac{3-\sqrt{13}}{2}}$ unless the sequence has an undefined term. To get an idea of why, try solving the equation ${\displaystyle \frac{r+1}{r-2}}=r$ for $r$ (this can be rearranged to a quadratic equation in $r$). There are infinitely many values of $r_1$ for which $r_n$ is undefined. The first few of them are $$2,5,\frac{11}{4},\frac{26}{7},\frac{59}{19},\frac{137}{40},\frac{314}{97},\frac{725}{217},\dots$$ Can you determine how these values are calculated? You might be interested in computing decimal approximations of these values and looking for a pattern.

   As a final remark, we note that not all sequences are "well-behaved" (either periodic or approaching some value). For an example of a more chaotic sequence, try exploring the example in part (a) a little further. Can you see any pattern at all?