2001 SMT/Algebra Problems/Problem 5

Problem

Let $f \colon \mathbb{N} \to \mathbb{N}$ be defined by $f(n) =\begin{cases}2 & \text{if }x = 0, \\(f(x-1))^2 & \text{if }x \neq 0 \end{cases}$ . What is $\log_2f(11)$ ?

Solution

Notice that each time we increase $x$ by $1$ starting fro $0$ , we square some power of $2$ . By playing around with the recursion, we can come up with an explicit formula $f(x)=2^{2^x}$ . Then $f(11)=2^{2^{11}}=2^{2048}$ , so $\log_2f(11)=\boxed{2048}$ .

~ eevee9406

Page

Toolbox

Search

2001 SMT/Algebra Problems/Problem 5

Problem

Solution