Review question

# How many numbers $n$ satisfy $f(n)=16$? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R7906

## Solution

The function $f$, defined for whole positive numbers, satisfies $f(1)=1$ and also the rules $f(2n)=2f(n),$ $f(2n+1)=4f(n),$ for all values of $n$. How many numbers $n$ satisfy $f(n)=16$?

1. $3$,

2. $4$,

3. $5$,

4. $6$.

To begin with, we could calculate the first few terms: $f(1)=1$, $f(2)=2$, $f(3)=2$, $f(4)=4$. Is there a pattern? Not an obvious one.

It’s a help to ask how 16 factorises. We can do this using only the factors of $2$ and $4$ in $5$ different ways, where the order matters, namely

1. $2\times 2\times 2\times 2$,
2. $4\times 2\times 2$,
3. $2\times 4\times 2$,
4. $2\times 2\times 4$ and
5. $4\times 4$.

To which values of $n$ do these correspond?

1. corresponds to applying the first rule, namely $f(2n)=2f(n)$, four times, giving $n=2\times 2\times 2\times 2\times 1=16$ (the sequence of $n$ values is $1-2-4-8-16$).

2. corresponds to applying the second rule once, followed by the first one twice, giving $n=2(2\times2\times1)+1=9$ (the sequence is $1-2-4-9$).

3. corresponds to applying the first rule, the second rule, and then the first one again, giving $n=2[2(2\times1)+1)]=10$ (the sequence is $1-2-5-10$).

4. corresponds to applying the first one twice, followed by the second one once, giving $n=2\times2\times[2(1)+1]=12$ (the sequence is $1-3-6-12$).

5. corresponds to applying the second rule twice, giving $n=2[2(1)+1]+1=7$ (the sequence is $1-3-7$).

Therefore we can have $f(n)=16$ for $5$ different values of $n$, and the answer is (c).

Alternatively, we can find $f(n)$ for $n = 1$ to $16$, and notice that $f(n) \geq 16$ for $n = 8$ to $16$.

This means that $f(n) > 16$ for $n = 17$ to $32$, since applying the first rule to one of these numbers $n$ gives $f(n)$ to be at least $32$, and applying the second rule gives $f(n)$ to be at least $64$.

We can extend this argument naturally to show $f(n) > 16$ for all $n > 16$, and so there are just five values of $n$ where $f(n) = 16$. The answer is (c).