Find the generating function for the amount of numbers that you get from 1 by applying $f(x)=2x-1$ and $g(x)=4x+1$ that are less than $2^n$

Question

Let S be the set of all positive integers that can be obtained from 1 by repeatedly applying the operations $f(x)=2x—1$ and $g(x)=4x+1$ in any order. Let $s_n=∣S∩[2^n]∣$. Find the ordinary generating function $S(x)=\displaystyle\sum_{n⩾0}s_nx^n$

I've noticed that if I apply f(x) to 1 I just get 1 every time and if I apply g(x) to 1 n times I get $\dfrac{4^{n+1} -1}{3}$

Answer 1

Completely revised. Last night I overlooked $85$ and led the reader up the garden path.

HINT: There may be slicker ways to see what’s going on, but here is a fairly straightforward approach if one doesn’t see any. First calculate a reasonably large initial segment of $S$:

$$\begin{array}{rcc} x:&1&5&9&21&17&37&41&85&33&65\\ f(x):&1&9&17&41&33&73&81&169&65&129\\ g(x):&5&21&37&85&69&149&165&341&133&261 \end{array}$$

To make this table I started with $1$ and calculated $f(1)$ and $g(1)$; $f(1)$ is just $1$ again, but $g(1)=5$, so I added that to the top row and repeated the process. This time both $f(5)=9$ and $g(5)=21$ were new, so I added both to the top row and continued. Notice that this process does not generate $S$ in increasing order: we get $21$ before we get $17$ for instance. However, it’s not too hard to verify that the top line contains every member of $S$ less than or equal to $65$, and hence that

$$S\cap[129]=\{1,5,9,17,21,33,37,41,65,69,73,81,85,129\}\;.$$

(As usual, $[n]=\{1,2,\ldots,n\}$.)

There’s no really obvious pattern, but one can notice that $S$ contains $5,9,17,33,65$, and $129$, these numbers being $1$ more than $2^2,2^3,2^4,2^5,2^6$, and $2^7$, respectively. This suggests that powers of $2$ might be relevant. Moreover, we’re specifically interested in $s_n=\big|S\cap[\color{crimson}{2^n}]\big|$ for $n\in\Bbb N$, and the functions $f$ and $g$ also clearly involve two powers of $2$, so (as stewbasic suggested) we might try looking at the members of $S$ in binary:

$$\begin{array}{c|r} \text{decimal}&\text{binary}\\ \hline 1&1\\ 5&101\\ 9&1001\\ 17&10001\\ 21&10101\\ 33&100001\\ 37&100101\\ 41&101001\\ 65&1000001\\ 69&1000101\\ 73&1001001\\ 81&1010001\\ 85&1010101\\ 129&10000001 \end{array}$$

Now we can see a pattern: it seems that we’re getting every odd binary number that does not have two consecutive $1$s. It’s clear from $f$ and $g$ that $S$ contains only odd numbers. Suppose that $x$ is an odd integer whose binary representation $b_1b_2\ldots b_n$ does not have two consecutive $1$s; note that $b_n=1$.

• Show that $g(x)$ has the binary representation $b_1b_2\ldots b_n01$.
• Show that $f(x)$ has the binary representation $b_1b_2\ldots b_{n-1}01$.

This clearly implies that every member of $S$ is an odd integer whose binary representation $b_1b_2\ldots b_n$ does not have two consecutive $1$s.

• Show that every such integer is in $S$, so that $S$ is precisely the set of such integers.

Let $a_n$ be the number of elements of $S$ whose binary representations (without leading zeroes) have $n$ digits.

• Show that $a_n=a_{n-1}+a_{n-2}$ for $n\ge 3$.
• Show that $$s_n=\sum_{k=1}^na_k\;.$$

Again, it never hurts to take a look at some actual numbers:

$$\begin{array}{rcc} n:&1&2&3&4&5&6&7&8\\ a_n:&1&0&1&1&2&3&5&8\\ s_n:&1&1&2&3&5&8&13&21 \end{array}$$

Those values of $s_n$ should look very familiar, especially in connection with the recurrence for $a_n$. So, for that matter, should the $a_n$ for $n\ge 3$. Make and prove the obvious conjecture, and you can get your generating function very easily from one that you probably already know.

Answer 2

A hint too long to make a comment:

All $x\in S$ are odd. Write them in binary: $f$ changes the ending $1$ to $01$ (though starting from $x=1$ the first $0$ doesn't count!), while $g$ changes the ending $1$ to $101$. If $a_k$ is the number of $k$-digit members of $S$ we have $a_1=1,\,a_2=0$, and $\,a_k=a_{k-1}+a_{k-2}$ for $k\ge 3$.

As with the Fibonacci sequence, constants $A,\,B$ exist (finding them is an exercise) for which $a_k=A\varphi^k+B\left( -\varphi\right)^{-k}$ for $k\ge 1$ with $\varphi$ the Golden ratio. Then $s_n = \sum_{k\le n}a_k$, which is easily computed with geometric series. The result $\sum_{n\ge 0} \left( cx\right)^n = \frac{1}{1-cx}$ will eventually obtain $S$ as a rational function.