This week’s Fiddler is a problem about composing functions. Here it goes:

Consider $f(n) = 2n+1$ and $g(n) = 4n$. It’s possible to produce different whole numbers by applying combinations of $f$ and $g$ to $0$. How many whole numbers between $1$ and $1024$ (including $1$ and $1024$) can you produce by applying some combination of $f$’s and $g$’s to the number $0$?

Extra Credit:Now consider the functions $g(n) = 4n$ and $h(n) = 1−2n$. How many integers between $-1024$ and $1024$ (including $-1024$ and $1024$) can you produce by applying some combination of $g$’s and $h$’s to the number $0$?

My solution:

[Show Solution]

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

\]