Making something out of nothing

Initially, we must start by applying $f$, otherwise we would just stay at zero. So for all intents and purposes, we can assume we start at $1$. At this point, it helps to write numbers out in binary (base two).

• Applying $f(n)=2n+1$ has the net effect of tacking on a “1” to the end of the number in binary form, For example, if we start at $12$ (which is $1100$ in binary), then $f(12)=25$, which is $11001$ in binary.
• Applying $g(n)=4n$ has the net effect of tacking on a “00” to the end of the number in binary form, so for example, if we start at $3$ (which is $11$ in binary), then $g(3)=12$, which is $1100$ in binary.

Now back to the original problem. Our goal is to count how many numbers between $1$ and $1024$ we can reach using compositions of $f$ and $g$. Since $1024=2^{10}$, let’s consider the more general problem of asking how many numbers between $1$ and $2^n$ we can reach. Let’s call this number $a_n$. Let’s look at the reachable numbers that have $k$ digits, and organize them in a table (in base 2):
\[
\begin{array}{c|l}
\text{digits} & \text{reachable numbers} \\ \hline
1 & 1 \\
2 & 11 \\
3 & 111, 100\\
4 & 1111, 1001, 1100\\
5 & 11111, 10011, 11001, 11100, 10000\\
\end{array}
\]The number of entries in row $k$ is simply $F_k$, the $k^\text{th}$ Fibonacci number. To see why, observe that to get to row $k$, we can start with the entries from row $k-1$ and apply $f$ (add a “$1$” to the end), or we can start with the entries from row $k-2$ and apply $g$ (add a “$00$” to the end). Since the first two rows each have one entry, we get the standard Fibonacci sequence (1,1,2,3,5,8,13,…).

Counting the reachable numbers up to $2^n-1$ means including all numbers with up to $n$ digits, so summing $F_1+F_2+\cdots+F_{n}$. However, we also want to include $2^n$. It’s clear from the pattern that this number is reachable whenever $n$ is even. Therefore, the reachable numbers $a_n$ is given by:
\[
a_n = F_1+\cdots+F_{n} + \begin{cases}
1 & n\text{ is even} \\
0 & n\text{ is odd}
\end{cases}
\]We can simplify this sum further. To see how, write:
\begin{align}
F_n &= F_{n+2}-F_{n+1}\\
F_{n-1} &= F_{n+1}-F_n \\
F_{n-2} &= F_n-F_{n-1} \\
\vdots\,\, &= \,\,\vdots\\
F_2 &= F_4-F_3\\
F_1 &= F_3-F_2
\end{align}Summing both sides, we get cancelations on the right-hand side:
\[
F_1+\cdots+F_{n} = F_{n+2}-F_2 = F_{n+2}-1
\]Therefore, we can simplify our formula and write:
\[
a_n = F_{n+2}-1+\frac{1}{2}\left( (-1)^n+1 \right)
\]Further simplification gets us our final answer:

$\displaystyle
a_n = F_{n+2}+\frac{1}{2}\left( (-1)^n-1 \right)
$

We can also find a closed-form expression if we use Binet’s formula:

$\displaystyle
a_n = \frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}}+\frac{(-1)^n-1}{2}
$

where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$ are the golden ratio and its conjugate, respectively. The first several values of $a_n$ are:
\[
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
a_n & 1 & 1 & 3 & 4 & 8 & 12 & 21 & 33 & 55 & 88 & 144 \\
\end{array}
\]

The original problem asked about numbers up to $1024 = 2^{10}$, so we have:
\[
a_{10} = F_{12} = 144
\]

Extra credit

This problem is similar to the first part, but we have to take a bit more care with edge cases. In particular, the first part had the nice feature that applying $f$ always added one digit, and applying $g$ always added two digits (in base 2). This is (almost) still true. Applying $g$ still adds two digits, but applying $h$ does the following:

• If the number is negative, it adds a one and flips the sign. For example: $h(-10)=21$ i.e., $-1010\mapsto 10101$.
• If the number is positive, it adds a zero, flips the sign, then subtracts $1$. For example: $h(6)=-11$, i.e., $110\mapsto -1011$.

It can happen that applying $h$ will not increase the number of digits. For example, $h(4)=-7$, i.e., $100\mapsto -111$. Nevertheless, we can still make a table similar to how we did before, except we will not arrange numbers by digits. Instead, arrange them in such a way that the Fibonacci pattern remains true, like this:
\[
\begin{array}{c|l}
\text{row} & \text{reachable numbers} \\ \hline
0 & 1 \\
1 & -1 \\
2 & 11, 100 \\
3 & -101, -111, -100 \\
4 & 1011, 1111, 1001, 1100, 10000 \\
5 & -10101, -11101, -10001, -11001, -11111, -10100, -11100, -10000 \\
\end{array}
\]Note that the rows alternate positive and negative numbers. Also, row $k$ for $k\geq 1$ contains numbers with $k$ binary digits, except the even rows, which also contain the number $2^{k}$, which has $k+1$ digits. The reason for this discrepancy is so that we maintain the Fibonacci pattern. Now, we can see that row $k$ is formed by applying $h$ to row $k-1$, or applying $g$ to row $k-2$. Therefore, row $k$ contains $F_{k+1}$ numbers.

Now, we can see that summing rows $0$ through $k$ will give us reachable numbers between $-(2^{k}-1)$ and $2^{k}$. To make sure we include $-2^{k}$, we should also add one whenever $k$ is even. So far, we counted positive and negative reachable numbers, but what about zero? Since $g(0)=0$, zero is also reachable, so we should add one more to include it. Therefore, we find that:
\[
b_n = F_1+\cdots+F_{n+1} + 1 + \begin{cases}
1 & n\text{ is even} \\
0 & n\text{ is odd}
\end{cases}
\]Similarly to the previous case, we obtain the solution:

$\displaystyle
b_n = F_{n+3}+\frac{1}{2}\left( (-1)^n+1 \right)
$

or, using Binet’s formula,

$\displaystyle
b_n = \frac{\phi^{n+3}-\psi^{n+3}}{\sqrt{5}}+\frac{(-1)^n+1}{2}
$

The first several values of $b_n$ are:
\[
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
b_n & 3 & 3 & 6 & 8 & 14 & 21 & 35 & 55 & 90 & 144 & 234 \\
\end{array}
\]The original problem asked about numbers between $-1024$ and $1024$, so since $1024=2^{10}$, we have:
\[
b_{10} = F_{13}+1 = 234
\]