I get F(0)=0 from n=0 in i), then F(1)=1 from n=1 in iii). Then putting n=1 in i) and ii), I get F(4)=F(2)+F(1)=F(2)+F(1), and also F(2)=F(4)+1, implying F(2)=F(4), implying 0=1???

I am not following the logic used to state that F(2)=F(4)+1. I will try to get a proof for this problem in the next few days.

Well, I am having a heck of a time actually proving the statement to be true. I know what is going on in the problem, but can't actually develop a proof. Here is a tiny bit of what i have uncovered. $ F(2^{m+1}) = F_{m+1}$ Where $ F_{n}$ follows the fibonacci sequence. Also, putting all values of n such that $ F(4n) = F(3n),$ into binary creates an obvious pattern as follows. 0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010 in essence, it is creating every combination such that no two 1's touch each other within the numbers. This is very strongly tied into the fibonacci sequence, so if you are going to attempt a proof, you will definitely have to use that.

I'm not going to be extremely detailed in this, only main ideas: By induction we can show the following result: If $n = \sum_{i = 0}^\infty{\epsilon_i \cdot 2^i}$ ($\epsilon_i = 0, 1$) then $F(n) = \sum_{i = 0}^\infty{\epsilon_i \cdot f_i}$, where $f_0 = 1, f_1 = 1, f_{i+2} = f_{i+1}+f_i$, so the Fibonacci's shifted by 1. Nextly, the following inequality holds, and equality only when $n$ has no 2 consecutive 1's in binary: $F(3n) \le F(4n)$. You can show this directly by computing the binary expression of $n, 3n, 4n$ and using the above formula. So the number of number $n < 2^m$ (let's call it $u_m$) with no consecutive 1's, satisfy the recurrence $u_{i+2} = u_{i+1}+u_i$, where $u_1 = 1, u_2 = 2$, so $u_m = f_{m+1} = F(2^{m+1})$.

(8 year bump) Does this work? Let $n$ be good if $F(4n)=F(3n)$. We claim that $F(2^n)=F_{n+1}$, where $F_n$ is the nth Fibonacci number, and $F(n) = F(n-2^m) + F(2^m)$ for all $n$ otherwise. The proof of the first part is obvious by induction. For the second part, assume this holds until $2^m$. Then, $F(4k+4) - F(4k) = F(2k+2) - F(2k) + F(k+1) - F(k)$ $F(4k + 4 - 2^m) - F(4k - 2^m) = F(2k+2-2^{m-1}) - F(2k - 2^{m-1}) + F(k + 1 - 2^{m-2}) - F(k - 2^{m-2})$ and by our induction hypothesis, we get that $F(4k) = F(4k - 2^m) + c$ for some constant $c$. Substituting $k=2^m$, we find that $c=F(2^m)$. Combining that with the fact that $F(4k+1)=F(4k+2)=F(4k)+1$ and $f(4k+3) = F(4k)+2$, this completes the proof for the second part. Now, once again we use induction to prove the main problem statement. By our induction hypothesis, we know that $0\leq n < 2^{m-1}$ has $F(2^m)$ good numbers. We wish to show that $2^{m-1}\leq n < 2^m$ has $F(2^{m-1})$ good numbers. Suppose $k$ is a good number from $0 \leq n < 2^{m-1}$, then $F(k+2^{m-1}) = F(k) + F(2^{m-1})$ $F(\frac 34(k+2^{m-1}) = F(\frac 34 k) + F(2^{m-2}) + F(2^{m-3})$ and since $F(2^{m-1}) = F(2^{m-2}) + F(2^{m-3})$ we are done.

This is merely a sketch (it takes a lot more tedious explanations of cases in the part about consecutive ones), but it works. You can work out the details if you want. Suppose $n$ can be respresented in base two as $(a_ka_{k-1}a_{k-2}\dots {a_0})_2.$ Let $F$ be the fibonacci sequence: $P_0=P_1=1$ and $P_n=P_{n-1}+P_{n-2}$ for $n\ge 2.$ We claim that \[F(n)=\sum_{i=0}^{k}{a_0P(0)}\]First, note that from the first relation $F(0)=0$ and so we have $F(1)=1,F(2)=1,F(3)=2.$ Note that these all satisfy our claimed function. Now, we proceed with induction: Base Case: Obviously, $n=0,1,2,3$ satisfies. Induction Hypothesis: Suppose the claim is true for all $1,2,\dots,4n-1$. Induction Step: Now, look at $4n,4n+1,4n+2,4n+3:$ Note that $F(4n)=F(2n)+F(n).$ Note that $4n=(a_ka_{k-1}a_{k-2}\dots {a_0}00)_2.$ Then \[F(4n)=\sum_{i=0}^{k}{P(i+1)a_i}+F(4n)+\sum_{i=0}^{k}{P(i)a_i}=\sum_{i=0}^{k}{P(i+2)a_i}\]as desired. Now, the conclusion follows for $F(4n+1),F(4n+2),F(4n+3)$ very simply. Now, we claim that for all $n$ such that its base two representation has no consecutive ones, $F(3n)=F(2n)+F(n).$ Given the function of multiplying a base two number by three, we note that if there are no consecutive ones, the result copies the input, but the digit to the left of each one there is another one. Therefore, $F(3n)$ can be expressed as the sum of $P(i)a_i$ of the input and $P(i+1)a_i$ of the input, so $F(3n)=F(n)+F(2n)$ as desired. Note that for each one in the input, the maximum amount of contribution it can give to the output is just $P(i)a_i+P(i+1)a_i$ and any consecutive ones will deviate from this maximum. Thus, $F(3n)=F(n)+F(2n)$ iff there are no consecutive ones in the representation of $n.$ It's easy to count the number of these that work, the result follows.

Let $F_n$ be the Fibonacci numbers where $F_0=F_1=1$. Denote $\&$ as bitwise AND and $|$ as bitwise OR. Claim. Let $n$ be $(\dots a_2 a_1 a_0)_2$ in binary. Then $F(n)=F_0 a_0+F_1 a_1+F_2 a_2+\dots$ Proof. Just verify the three properties. Claim. For all $a,b$, $F(a)+F(b)\ge F(a+b)$. Equality occurs when $a\&b=0$, or $a\&b=2$ and $(a|b)\&4=0$. Proof. Just check this with the previous claim. Now note that $F(3n)=F(2n+n)\le F(2n)+F(n)=F(4n)$, so $n\&(2n)=0$(this implies that there is no $11$ substring in the binary representation of $n$), or $a\&b=2$(this implies that $n\equiv 3\pmod 4$) and $(a|b)\&4=0$(this is therefore impossible). Therefore, $F(3n)=F(4n)$ if and only if there is no $11$ substring in the binary representation of $n$. Thus if the number of $n$ with exactly $m$ digits in binary is $a_m$, then $a_0=1$(where $n=0$), $a_1=1$, $a_2=1$, and $a_m=a_{m-2}+a_{m-3}+\dots+a_1$ for all $m\ge 3$. Thus $a_m=a_{m-2}+a_{m-1}$. The number of $n<2^m$ that works is then \[ a_0+a_1+\dots+a_m =1+F_0+F_1+F_2+\dots+F_{m-1} =F_{m+1} =F(2^{m+1}).\;\blacksquare \]

Here is a proof without the binary representation of $n$, albeit, a much more convoluted one: Claim 1. $F(4n+3)\ge F(4n+4)$ for all $n\in\mathbb{N}_0$. Proof: We proceed by induction on $n$. The claim obiously holds for $n=0$, as $F(3)=2=F(4)$. Assume the claim holds for all nonnegative integers less than $n$, where $n\ge 1$. \begin{align*} F(4n+3)\ge F(4n+4) &\iff F(2n)+F(n)+2\ge F(2n) + F(n+1) + 1 \\ &\iff F(n) + 1\ge F(n+1) \end{align*}The last inequality holds by definition if $n+1$ is not of the form $4t+4$. If it is, then the inductive hypothesis implies $F(n)+1\ge F(n+1)+1>F(n+1)$, hence the claim holds for $n$ too. $\square$ Claim 2. For each $n\in\mathbb{N}_0$: $\bullet\quad F(n)+1\ge F(n+1),$ $\bullet\quad F(n)+1\ge F(n+2),$ $\bullet\quad F(2n+1)\ge F(2n+2).$ Proof: This follows immediately from the definition of $F$ and claim 1. $\square$ Claim 3. $F(4n)\ge F(3n)$ for each $n\in\mathbb{N}_0$. If $n$ is of the form $4t+3$, then the inequality becomes strict. Proof: For $n=0$, the claim trivially holds. Now assume it holds for each nonnegative integer less than $n$, where $n\ge 1$. If $n=4t$: \begin{align*} F(4n)&=F(16t)=F(8t)+F(4t)\stackrel{\mathclap{\normalfont\mbox{hyp.}}}{\ge} F(6t)+F(3t)=F(12t)=F(3n). \end{align*} If $n=4t+1$: \begin{align*} F(4n)&=F(16t+4)=F(8t+2)+F(4t+1)=F(8t)+F(4t)+2\\ &\stackrel{\mathclap{\normalfont\mbox{hyp.}}}{\ge}F(6t)+F(3t)+2=F(12t)+2=F(12t+3)=F(3n). \end{align*} If $n=4t+2$: \begin{align*} F(4n)&=F(16t+8)=F(8t+4)+F(4t+2)=F(8t+4)+F(4t)+1\\ &\stackrel{\mathclap{\normalfont\mbox{hyp.}}}{\ge}F(6t+3)+F(3t)+1\stackrel{\mathclap{\normalfont\mbox{2}}}{\ge}F(6t+2)+F(3t+1)+1\\ &=F(12t+4)+1=F(12t+6)=F(3n). \end{align*} If $n=4t+3$: \begin{align*} F(4n)&=F(16t+12)=F(8t+6)+F(4t+3)=F(8t+4)+F(4t)+3\\ &\stackrel{\mathclap{\normalfont\mbox{hyp.}}}{\ge}F(6t+3)+F(3t)+3\stackrel{\mathclap{\normalfont\mbox{2}}}{\ge}F(6t+4)+F(3t)+3\\ &\stackrel{\mathclap{\normalfont\mbox{2}}}{\ge}F(6t+4)+F(3t+2)+2=F(12t+8)+2\\ &=F(12t+9)+1=F(3n+1)>F(3n). \end{align*} Hence the claim holds for $n$ as well. This closes the induction. $\square$ Denote the condition $F(4n)=F(3n)$ by $P(n)$. Claim 4. $P(n)\iff P(2n)\iff P(4n+1)$, for each $n\in\mathbb{N}_0$. Proof: The claim holds for $n=0$. Assume it holds for each nonnegative integer less than $n$, where $n\ge 1$. First we claim $P(n)\iff P(2n)$. If $n=4t$: $\bullet\quad$ if $P(n)$ holds, then $P(2t)$ also holds by the induction hypothesis, hence $$F(32t)=F(16t)+F(8t)=F(12t)+F(6t)=F(24t),$$so $P(2n)$ holds. $\bullet\quad$ if $P(2n)$ holds, then, similarly to above, $F(16t)+F(8t)=F(12t)+F(6t)$, so by claim 3, $F(16t)=F(12t)$, i.e., $P(n)$ holds. If $n=4t+1$: $\bullet\quad$ if $P(n)$ holds, then $P(t)$ also holds by the induction hypothesis, hence \begin{align*} F(32t+8)&=F(16t+4)+F(8t+2)=F(16t+4)+F(8t)+1\\&=F(12t+3)+F(6t)+1=F(12t+2)+F(6t+1)+1\\&=F(24t+4)+1=F(24t+6), \end{align*}hence $P(2n)$ also holds. $\bullet\quad$ if $P(2n)$ holds, then, as above, $F(16t+4)+F(8t+2)=F(12t+3)+F(6t)$, so by claim 3, $F(16t+4)=F(12t+3)$, i.e., $P(n)$ holds. If $n=4t+2$: $\bullet\quad$ if $P(n)$ holds, then $P(2t+1)$ also holds by the the induction hypothesis, so $$F(32t+16)=F(16t+8)+F(8t+4)=F(12t+6)+F(6t+3)=F(24t+12),$$hence $P(2n)$ holds too. $\bullet\quad$ if $P(2n)$ holds, then, as above, $F(16t+8)+F(8t+4)=F(12t+6)+F(6t+3)$, so by claim 3, $F(16t+8)=F(12t+6)$, i.e., $P(n)$ holds. Finally, if $n=4t+3$, then $P(n)$ doesn't hold (by claim 3). Furthermore, \begin{align*} F(32t+24)&=F(16t+12)+F(8t+6)=F(16t+12)+F(8t+5),\\ F(24t+18)&=F(24t+16)+1=F(12t+8)+F(6t+4)+1=F(12t+9)+F(6t+4),\\ F(16t+12)&\stackrel{\mathclap{\normalfont\mbox{3}}}{>}F(12t+9),\\ F(8t+5)&=F(8t+4)+1\stackrel{\mathclap{\normalfont\mbox{3}}}{\ge}F(6t+3)+1\stackrel{\mathclap{\normalfont\mbox{2}}}{\ge}F(6t+4), \end{align*}putting these together yields $F(32t+24)>F(24t+18)$, so $P(2n)$ also doesn't hold. Next we claim $P(n)\iff P(4n+1)$. Notice that \begin{align*} P(4n+1)&\iff F(16n+4)=F(12n+3)\\ &\iff F(8n+2)+F(4n+1)=F(12n)+3\\ &\iff F(8n)+F(4n)=F(6n)+F(3n). \end{align*}If $P(4n+1)$ holds, then $P(n)$ holds too by claim 3 and the above equivalence. Also, if $P(n)$ holds, then $P(2n)$ holds too, so $P(4n+1)$ also holds by claim 3 and the above equivalence. Therefore, $P(n)\iff P(2n)\iff P(4n+1)$, which closes the induction. $\square$ Let $A_m=\{n\in\mathbb{N}_0\colon 2^m\le n<2^{m+1}\land P(n)\}$ and let $a_m=\lvert A_m\rvert$ for each $m\in\mathbb{N}_0.$ Claim 5. $a_m = a_{m-1}+a_{m-2}$ for each $m\in\mathbb{N}$, $m\ge 2$. Proof: We construct a bijection $f\colon A_{m-2}\cup A_{m-1}\to A_m$ defined with $f(n)=4n+1$ for $n\in A_{m-2}$, and $f(n)=2n$ for $n\in A_{m-1}$. Such an $f$ is well defined, as for $n\in A_{m-2}$, we have $2^{m-2}\le n\le 2^{m-1}-1,$ so $2^m<2^m+1\le 4n+1\le 2^{m+1}-3<2^{m+1}.$ By claim 4, $P(4n+1)$ follows from $P(n)$, so $4n+1\in A_m$. For $n\in A_{m-1}$, we have $2^{m-1}\le n< 2^{m}$, so $2^m\le 2n<2^{m+1}$. By claim 4, $P(2n)$ follows from $P(n)$, so $2n\in A_m$. $f$ is obviously injective. It is surjective, as no number of the form $4n+3$ is in $A_m$, and each number of the form $4n+1$, $2n$ that is in $A_m$ has a corresponding $n$ in $A_{m-2}, A_{m-1}$ respectively. Therefore, $f$ is bijective, and as $A_{m-2}$ and $A_{m-1}$ are disjoint, $a_m=a_{m-1}+a_{m-2}$. $\square$ Claim 6. $a_m=F(2^m)$ for each $m\in\mathbb{N}_0$. Proof: By induction, taking into account the definition of $F$ and the recursion from claim 5. $\square$ Finally, by claim 6, the number of integers $n$ with $0\le n<2^m$ and $P(n)$ is: \begin{align*} 1+a_0+a_1+\dots+a_{m-1}&=1+F(1)+F(2)+\dots+F(2^{m-1})\\&=F(1)+2F(2)+F(4)+\dots+F(2^{m-1})\\&=F(2)+2F(4)+F(8)+\dots+F(2^{m-1})\\&=\dots\\&=F(2^{m-2})+2F(2^{m-1})\\&=F(2^{m-1})+F(2^m)\\&=F(2^{m+1}). \end{align*} Which concludes the proof. $\blacksquare$