Two sequences are defined by \(a_1 = 1\) and \(b_1 = 2\) and, for \(n \ge 1\),
\begin{equation*}
\begin{split}
a_{n+1} & = a_n+ 2b_n \,,
\\
b_{n+1} & = 2a_n + 5b_n \,.
\end{split}
\end{equation*}
Prove by induction that, for all \(n \ge 1\),
\[ a_n^2+2a_nb_n - b_n^2 = 1 \,. \tag{\(*\)}\]
Let \(c_n = \dfrac{a_n}{b_n}\). Show that \(b_n \ge 2 \times 5^{n-1}\) and use \((*)\) to show that
\[ c_n \to \sqrt 2 -1 \text{ as } n\to\infty\,. \]
Show also that \(c_n > \sqrt2 -1\) and hence that \(\dfrac2 {c_n+1} < \sqrt2 < c_n+1\).
Deduce that \(\dfrac{140}{99}< \sqrt{2} < \dfrac{99}{70 }\,\).
Solution: Claim \(a_n^2+2a_nb_n - b_n^2 = 1\) for all \(n \geq 1\)
Proof: (By induction)
Base case: (\(n = 1\)).
When \(n = 1\) we have \(a_1^2 + 2a_1 b_1-b_1^2 = 1^2+2\cdot1\cdot2-2^2 = 1\) as required.
(Inductive step). Now we assume our result is true for some \(n =k\), ie \(a_k^2+2a_kb_k - b_k^2 = 1\), now consider \(n = k+1\)
\begin{align*}
&& a_{k+1}^2+2a_{k+1}b_{k+1} - b_{k+1}^2 &= (a_k+2b_k)^2+2(a_k+2b_k)(2a_k+5b_k) - (2a_k+5b_k)^2 \\
&&&= a_k^2+4a_kb_k+4b_k^2 +4a_k^2+18a_kb_k+20b_k^2 - 4a_k^2-20a_kb_k-25b_k^2 \\
&&&= (1+4-4)a_k^2+(4+18-20)a_kb_k +(4+20-25)b_k^2 \\
&&&= a_k^2+2a_kb_k -b_k^2 = 1
\end{align*}
Therefore since our statement is true for \(n = 1\) and when it is true for \(n=k\) it is true for \(n=k+1\) by the POMI it is true for \(n \geq 1\)
Notice that \(b_{n+1} \geq 5 b_n\) and therefore \(b_n \geq 5^{n-1} b_1 = 2\cdot 5^{n-1}\), so
\begin{align*}
&& 1 &= a_n^2+2a_nb_n - b_n^2\\
\Rightarrow && \frac1{b_n^2} &= c_n^2 + 2c_n - 1 \\
\to && 0 &= c_n^2 + 2c_n - 1 \quad \text{ as } n\to \infty \\
\end{align*}
This has roots \(c = -1 \pm \sqrt{2}\), and since \(c_n > 0\) it must tend to the positive value, ie \(c_n \to \sqrt{2}-1\)
Notice that \(c_n^2 + 2c_n - 1 > 0\) so either \(c_n > \sqrt{2}-1\) or \(c_n < -1-\sqrt{2}\), but again, since \(c_n > 0\) we must have \(c_n > \sqrt{2}-1\).
Therefore \(\sqrt{2} < c_n + 1\) and \(1+c_n > \sqrt{2} \Rightarrow \frac{1}{1+c_n} < \frac{\sqrt{2}}2 \Rightarrow \frac{2}{1+c_n} < \sqrt{2}\)
\begin{array}{c|c|c}
n & a_n & b_n \\ \hline
1 & 1 & 2 \\
2 & 5 & 12 \\
3 & 29 & 70
\end{array}
Therefore \(c_3 = \frac{29}{70}\) and so
\(\frac{2}{1 + \frac{29}{70}} = \frac{140}{99} < \sqrt{2} < \frac{29}{70} + 1 = \frac{99}{70}\)
In the following argument to show that \(\sqrt2\) is irrational, give proofs appropriate for steps 3, 5 and 6.
Assume that \(\sqrt2\) is rational.
Define the set \(S\) to be the set of positive integers with the following property:
\(n\) is in \(S\) if and only if \(n \sqrt2\) is an integer.
Show that the set \(S\) contains at least one positive integer.
Define the integer \(k\) to be the smallest positive integer in \(S\).
Show that \((\sqrt2-1)k\) is in \(S\).
Show that steps 4 and 5 are contradictory and hence that \(\sqrt2\) is irrational.
Prove that \(2^{\frac13} \) is rational if and only if \(2^{\frac23}\) is rational.
Use an argument similar to that of part (i) to prove that \(2^{\frac13}\) and \(2^{\frac23}\) are irrational.
Solution:
For step 3, since we have assumed \(\sqrt{2}\) is rational we can write it in the form \(p/q\) with \(p, q\) coprime with \(q \geq 1\). Then \(q \in S\) since \(q\sqrt{2} = p\) which is an integer.
For step 5, notice that \((\sqrt{2}-1)k\) is an integer (since \(\sqrt{2}k\) is an integer and so is \(-k\). It is also positive since \(\sqrt{2} > 1\). We must check that \((\sqrt{2}-1)k \cdot \sqrt{2} = 2k - \sqrt{2}k\) is also an integer, but clearly it is as both \(2k\) and \(-\sqrt{2}k\) are integers. Therefore \((\sqrt{2}-1)k \in S\).
For step 6, notice that \((\sqrt{2}-1) < 1\) and therefore \((\sqrt{2}-1)k < k\), contradicting that \(k\) is the smallest element in our set. (And all non-empty sets of positive integers have a smallest element)
Claim: \(2^{\frac13}\) is irrational \(\Leftrightarrow 2^{\frac23}\) is irrational.
Proof: Since \(2^{\frac13} \cdot 2^{\frac23} = 2\) if one of them is rational, then the other one must also be rational. Which is the same as them both being irrational at the same time.
Assume that \(\sqrt[3]{2}\) is rational, ie \(\sqrt[3]{2} = p/q\) for some integers.
\(S := \{ n \in \mathbb{Z}_{>0} : n \sqrt[3]{2} \text{ and } n \sqrt[3]{4}\in \mathbb{Z}\}\)
Suppose \(k\) is the smallest element in \(S\) (which must exist, consider \(q^2\)
Consider \((\sqrt[3]{2}-1)k\) then clearly this is an integer, and \((\sqrt[3]{2}-1)\sqrt[3]{2}k = \sqrt[3]{4}k - \sqrt[3]{2}k \in \mathbb{Z}\) and \((\sqrt[3]{2}-1)\sqrt[3]{4}k = 2 k -\sqrt[3]{4}k \in \mathbb{Z}\).
But this is a smaller element of \(S\), contradicting that \(k\) is the smallest element. Therefore, we have a contradiction.