Let
$f_0(x) = x^2$ and $f_n(x) = f_{n-1}(f_{n-1}(x))$ for $n > 0.$ How many digits are in the number $f_n(10)$ for a given $n \ge 0?$
-
Have you tried finding the general formula for
$f_n(x)?$ -
How many digits does
$10^n$have?
-
We can work out the general formula for
$f_n(x)$and then substitute$x=10$:$$\begin{aligned} f_1(x)&=(x^2)^2=x^4 \\ f_2(x)&=(x^4)^4=x^{16} \\ f_3(x)&=(x^{16})^{16}=x^{256} \\ &\ldots \\ f_n(x)&=x^{2^{2^n}} \\ \end{aligned}$$We could show that our “guess” satisfies the recurrence relation:
$$\begin{aligned} f_n(x)&=f_{n-1}(f_{n-1}(x)) \\ &=\big(x^{2^{2^{n-1}}}\big)^{2^{2^{n-1}}} \\ &= x^{2^{2^{n-1}} \cdot {2^{2^{n-1}}}} \\ &=x^{2^{2^n}} \\ \end{aligned}$$The answer is thus
$2^{2^n}+1$digits.