20. Let $\left\{a_{n}\right\}$ and $\left\{b_{n}\right\}$ be sequences defined recursively by $a_{0}=2 ; b_{0}=2$, and $a_{n+1}=a_{n} \sqrt{1+a_{n}^{2}+b_{n}^{2}}-b_{n}$; $b_{n+1}=b_{n} \sqrt{1+a_{n}^{2}+b_{n}^{2}}+a_{n}$. Find the ternary (base 3) representation of $a_{4}$ and $b_{4}$.
Answer: 1000001100111222 and 2211100110000012
Note first that $\sqrt{1+a_{n}^{2}+b_{n}^{2}}=3^{2^{n}}$. The proof is by induction; the base case follows trivially from what is given. For the inductive step, note that $1+a_{n+1}^{2}+b_{n+1}^{2}=1+a_{n}^{2}\left(1+a_{n}^{2}+b_{n}^{2}\right)+b_{n}^{2}-2 a_{n} b_{n} \sqrt{1+a_{n}^{2}+b_{n}^{2}}+$ $b_{n}^{2}\left(1+a_{n}^{2}+b_{n}^{2}\right)+a_{n}^{2}+2 a_{n} b_{n} \sqrt{1+a_{n}^{2}+b_{n}^{2}}=1+\left(a_{n}^{2}+b_{n}^{2}\right)\left(1+a_{n}^{2}+b_{n}^{2}\right)+a_{n}^{2}+b_{n}^{2}=\left(1+a_{n}^{2}+b_{n}^{2}\right)^{2}$. Invoking the inductive hypothesis, we see that $\sqrt{1+a_{n+1}^{2}+b_{n+1}^{2}}=\left(3^{2^{n}}\right)^{2}=3^{2^{n+1}}$, as desired.
The quickest way to finish from here is to consider a sequence of complex numbers $\left\{z_{n}\right\}$ defined by $z_{n}=a_{n}+b_{n} i$ for all nonnegative integers $n$. It should be clear that $z_{0}=2+2 i$ and $z_{n+1}=z_{n}\left(3^{2^{n}}+i\right)$. Therefore, $z_{4}=(2+2 i)\left(3^{2^{0}}+i\right)\left(3^{2^{1}}+i\right)\left(3^{2^{2}}+i\right)\left(3^{2^{3}}+i\right)$. This product is difficult to evaluate in
the decimal number system, but in ternary the calculation is a cinch! To speed things up, we will use balanced ternary ${ }^{1}$, in which the three digits allowed are $-1,0$, and 1 rather than 0,1 , and 2 . Let $x+y i=\left(3^{2^{0}}+i\right)\left(3^{2^{1}}+i\right)\left(3^{2^{2}}+i\right)\left(3^{2^{3}}+i\right)$, and consider the balanced ternary representation of $x$ and $y$. For all $0 \leq j \leq 15$, let $x_{j}$ denote the digit in the $3^{j}$ place of $x$, let $y_{j}$ denote the digit in the $3^{j}$ place of $y$, and let $b(j)$ denote the number of ones in the binary representation of $j$. It should be clear that $x_{j}=-1$ if $b(j) \equiv 2(\bmod 4), x_{j}=0$ if $b(j) \equiv 1(\bmod 2)$, and $x_{j}=1$ if $b(j) \equiv 0(\bmod 4)$. Similarly, $y_{j}=-1$ if $b(j) \equiv 1(\bmod 4), y_{j}=0$ if $b(j) \equiv 0(\bmod 2)$, and $y_{j}=1$ if $b(j) \equiv 3(\bmod 4)$. Converting to ordinary ternary representation, we see that $x=221211221122001_{3}$ and $y=110022202212120_{3}$. It remains to note that $a_{4}=2 x-2 y$ and $b_{4}=2 x+2 y$ and perform the requisite arithmetic to arrive at the answer above.