An endofunction on natural numbers defined by induction on $n$.

Question

A function $f \colon \mathbb{N} \to \mathbb{N}$ fulfils the following conditions, for all $n \in \mathbb{N}$:

1. $f(4n) = f(2n) + f(n)$;
2. $f(4n + 2) = f(4n) + 1$;
3. $f(2n + 1) = f(2n) + 1$.

Question 1: Show that the cardinality of the set $S_m := \{n \in \mathbb{N} \mid n < 2^m \text{ and } f(4n) = f(3n)\}$ is $f(2^{m+1})$.

Question 2: Is it true that $\lim_{n \to +\infty} f(n) = +\infty$?

In my opinion, the two questions, especially the first one, are really intriguing and challenging. I have no answer for either, just some preliminary remarks.

Remarks: The conditions above define $f$ by induction on $n$, since $f(0) = 0$ according to condition 1. For all $n > 0$, we have that:

• $f(n) = f(n-1) + 1$ if $n$ is odd (according to condition 3);
• $f(n) = f(n-1)$ if $n$ is even and not divisible by $4$ (according to conditions 2 and 3);
• $f(n)$ decreases with respect to $f(n-1)$ if $n$ divisible by $4$, but I'm not able to find a general law.

I conjecture that $f(2^n) = F(n)$ where $F(n)$ is the $n$th number of the Fibonacci sequence, but I don't have a proof of that

Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$Define $F(0) = 0$, $F(1) = 1$, $F(n) = F(n - 1) + F(n - 2)$ for $n \geqslant 2$. Setting $n = 0$ in the first recurrence relation yields $f(0) = 0$. Now it is not hard to prove by induction on $n$ that if the binary representation of $n$ is $(a_m \cdots a_0)_2$, then\begin{gather*}f(n) = \sum_{k = 0}^m a_k F(k + 1). \tag{1}\end{gather*}For question 2, since (1) implies $f(n) \geqslant F([\log_2 n] + 1)$, then $\lim\limits_{n → ∞} f(n) = +∞$. For question 1, the following lemma is needed.
Lemma: For any $a, b \in \mathbb{N}$,$$f(a + b) \leqslant f(a) + f(b)$$with the equality holds iff no carrying occurs at digits other than the second lowest digit when adding $a$ and $b$ in the binary system.
Proof: Without loss of generality, suppose $a = (a_m \cdots a_0)_2$ and $b = (b_m \cdots b_0)_2$ where $a_m = b_m = 0$. Define $c_{0, k} = a_k + b_k$ for $0 \leqslant k \leqslant m$. If $c_{j, 0}, \cdots, c_{j, m}$ are defined, then define$$c_{j + 1, j} = c_{j, j} \bmod 2,\ c_{j + 1, j + 1} = c_{j, j + 1} + \left[ \frac{c_{j, j}}{2} \right],\ c_{j + 1, k} = c_{j, k}\ (\forall k ≠ j, j + 1).$$Note that the $c_{j, k}$'s defined above implement the process of adding $a$ and $b$ in the binary system, and $a + b = (c_{m, m} \cdots c_{m, 0})_2$. For $0 \leqslant j < m$,\begin{align*}&\peq \sum_{k = 0}^m c_{j, k} F(k + 1) - \sum_{k = 0}^m c_{j + 1, k} F(k + 1)\\&= (c_{j, j} F(j + 1) + c_{j, j + 1} F(j + 2)) - (c_{j + 1, j} F(j + 1) + c_{j + 1, j + 1} F(j + 2))\\&= (c_{j, j} - c_{j + 1, j}) F(j + 1) - (c_{j + 1, j + 1} - c_{j, j + 1}) F(j + 2).\end{align*}If no carrying occurs at the $j$-th digit when adding $a$ and $b$, then $c_{j, j} = c_{j + 1, j}$ and $c_{j + 1, j + 1} = c_{j, j + 1}$, which imply$$\sum_{k = 0}^m c_{j, k} F(k + 1) = \sum_{k = 0}^m c_{j + 1, k} F(k + 1).$$Otherwise, $c_{j + 1, j} = c_{j, j} - 2$ and $c_{j + 1, j + 1} = c_{j, j + 1} + 1$, which imply\begin{align*}&\peq \sum_{k = 0}^m c_{j, k} F(k + 1) - \sum_{k = 0}^m c_{j + 1, k} F(k + 1)\\&= 2F(j + 1) - F(j + 2) = F(j + 1) - F(j).\end{align*}If $j = 1$, then $\sum\limits_{k = 0}^m c_{j, k} F(k + 1) = \sum\limits_{k = 0}^m c_{j + 1, k} F(k + 1)$. Otherwise $\sum\limits_{k = 0}^m c_{j, k} F(k + 1) > \sum\limits_{k = 0}^m c_{j + 1, k} F(k + 1)$.Thus$$\sum_{k = 0}^m c_{j, k} F(k + 1) \geqslant \sum_{k = 0}^m c_{j + 1, k} F(k + 1),$$where the equality holds iff $j = 1$ or no carrying occurs at the $j$-th digit when adding $a$ and $b$. Therefore,$$f(a) + f(b) = \sum_{k = 0}^m c_{0, k} F(k + 1) \geqslant \cdots \geqslant \sum_{k = 0}^m c_{m, k} F(k + 1) = f(a + b),$$where the equality holds iff no carrying occurs at digits other than the second lowest digit when adding $a$ and $b$.
Now back to question 2. Note that by definition, $f(4n) = f(2n) + f(n)$ for $n \in \mathbb{N}$. For any $m \in \mathbb{N}$, it can be proved by the lemma that\begin{align*}S_m &= \{n < 2^m \mid f(4n) = f(3n)\} = \{n < 2^m \mid f(3n) = f(2n) + f(n)\}\\&= \{n < 2^m \mid \text{No carrying occurs at digits other than the second lowest digit}\\&\peq \text{ when adding } 2n \text{ and } n\}\\&= \{n < 2^m \mid \text{No carrying occurs when adding } 2n \text{ and } n\}\\&= \{n < 2^m \mid \text{No two adjacent digits in the binary representation of } n \text{ are both } 1\},\end{align*}then it can be proved that $S_m = S_{m - 1} \cup (S_{m - 2} + 2^{m - 1})$ for $m \geqslant 2$, where $A + n := \{a + n \mid a \in A\}$. Since $S_{m - 1} \cap (S_{m - 2} + 2^{m - 1}) = \varnothing$, then$$|S_m| = |S_{m - 1}| + |S_{m - 2}|. \quad \forall m \geqslant 2$$By induction, $|S_m| = F(m + 2) = f(2^{m + 1})$ for $m \in \mathbb{N}$.

Answer 2

Although I don't have a complete proof of the result, I explain what I found so anyone can try to find the proof.

First, we compute some values of $f$ to use later on: $$ \begin{array}{|c|c|} \hline n & 0& 1 & 2 & 3 & 4& 5 & 6 & 7 & 8& 9 & 10 & 11\\ \hline f(n)& 0 & 1& 1 & 2 & 2& 3& 3& 4& 3& 4& 4& 5 \\ \hline \end{array} $$

Denote by $F(m):=f(2^{m})$ (as you as you did). So $F(0)=f(1)=1$, and $F(1)=f(2)=1$. Condition 1 says that, for $m\ge 1$, $$F(m+1)=f(2^{m+1})=f(4\cdot 2^{m-1})=f(2^{m})+f(2^{m-1})=F(m)+F(m-1),$$ so $\{F(m+1)\}$ is the Fibonacci sequence (usual Fibonacci sequence starts with $F_0=0$, $F_1=1$, so $F_2=1$). So all explicit formulae for the Fibonacci sequence applies.

We can describe explicitly the function $f$ in terms of $F$.

Explicit expression:

Let $1\le n<2^{m+1}$ be written in binary as $n:=\sum_{i=0}^m b_i 2^i$ for $b_i\in \{0,1\}$. Then $$f(n):=\sum_{i=0}^m b_i f(2^i)=\sum_{i=0}^m b_i F(i)$$

To show this formula one only needs to see it verifies the three properties of the definition. Properties 2 and 3 are easy. Only property 1 uses Fibonacci recurrence, as $$f(4n)=\sum_{i=0}^m b_i F(i+2)=\sum_{i=0}^m b_i (F(i)+F(i+1))=\sum_{i=0}^m b_i F(i+1)+\sum_{i=0}^m b_i F(i)=f(2n)+f(n).$$

Recall your notation: $$ S_m=\{n \in \mathbb{N} \mid n < 2^m \text{ and } f(4n) = f(3n)\}.$$

Now, I believe the following is true:

Conjecture:

Any $n\in S_m$ verifies that $3n<2^{m+1}$.

Note that this says there is a big gap between the largest element in $S_m$ and $2^m-1$. For example, if $m=5$, the largest element in $S_5$ is $21$, while $2^m-1=31$ (note $3\cdot 21=63<64=2^6$). And for $m=6$ we get that 42 is the largest element in $S_6$ and $3\cdot 42=126<128=2^7$. In fact it should be true that $$\lfloor \frac{2^{m+1}-1}{3}\rfloor\in S_m$$ so the largest $n$ verifying that $3n<2^{m+1}$ is in $S_m$.

Now, using the conjecture one can prove by induction the following result, which implies the answer to your question.

Assertion

For any $m\ge 1$ we have $$S_{m+1}=S_m\sqcup (S_{m-1}+2^m)$$ (where $S_{m-1}+2^m=\{n+2^m \ | \ n\in S_{m-1}\}$).

Observe that the union is disjoint because all the elements of $S_m$ are less than $2^m$, while the other set has all members bigger or equal to $2^m$. So we get $|S_{m+1}|=|S_m|+|S_{m-1}|$ and we are done, since $|S(m)|=F(m+1)$ is true for $m=0,1,2$ trivially.