Question 3 of 12

Question 3

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $a_0=2$, $a_{n+1}=a_n^{2}$ (each term is the square of the previous term).

Find. (a) closed form for $a_n$; (b) growth-rate classification against $2^n$ and $n^n$; (c) a lower bound on the number of distinct prime factors of $a_n-1$.

Approach. Unroll the recursion by repeated squaring to spot the closed form, then compare growth rates by taking logarithms; for (c), factor $a_n-1$ as a difference of squares and show the two factors are coprime, so each recursive step contributes at least one brand-new prime.

1. Part (a) — unroll the recursion. $a_1=a_0^2=2^2$, $a_2=a_1^2=2^4$, $a_3=a_2^2=2^8$ — each squaring doubles the exponent of 2, so after n squarings the exponent is $2^n$: $$\boxed{a_n = 2^{2^n}}$$
2. Part (b) — compare growth rates. Take $\log_2$ of each candidate bound at large n: $\log_2(2^n)=n$, $\log_2(n^n)=n\log_2 n$, while $\log_2(a_n)=2^n$. Since $2^n$ eventually exceeds any polynomial or quasi-linear function of n such as $n$ or $n\log_2 n$ (exponential beats "exponent that only grows linearly/log-linearly"), $a_n$ is not $O(2^n)$ and not $O(n^n)$: $$\boxed{a_n \ne O(2^n), \quad a_n \ne O(n^n)}$$ Numerically $a_7=2^{128}\approx3.4\times10^{38}$ while $7^7=823{,}543$ and $2^7=128$ — the gap widens super-exponentially with n.
3. Part (c) — induction using a coprime factorization. Base case $n=1$: $a_1-1=4-1=3$, which is prime, so $a_1-1$ has (at least) 1 distinct prime factor. Inductive step: since $a_n=a_{n-1}^2$, $$a_n-1 = a_{n-1}^2-1 = (a_{n-1}-1)(a_{n-1}+1).$$ Every $a_k$ ($k\ge0$) is even (it is a power of 2), so $a_{n-1}-1$ and $a_{n-1}+1$ are consecutive odd numbers differing by 2; any common divisor of both must divide their difference, $2$, but both are odd, so $$\gcd(a_{n-1}-1,\;a_{n-1}+1)=1.$$ By the inductive hypothesis $a_{n-1}-1$ already has at least $n-1$ distinct prime factors. Because $a_{n-1}+1$ is coprime to $a_{n-1}-1$ and greater than 1 (so it has at least one prime factor of its own), that prime factor cannot appear among the $n-1$ primes already counted. Hence the product $a_n-1=(a_{n-1}-1)(a_{n-1}+1)$ has at least $$\boxed{(n-1)+1 = n \text{ distinct prime factors}}$$ completing the induction.