elementary number theory - Proving or disproving $f(n)-f(n-1)le n, forall n gt 1$, for a recursive function with floors.

The Olympiad-style question I was given was as follows:

A function $f:\mathbb{N}\to\mathbb{N}$ is defined by $f(1)=1$ and for $n>1$, by: $$f(n)=f\left(\left\lfloor\frac{2n-1}{3}\right\rfloor\right)+f\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)$$ Is it true that $f(n)-f(n-1)\le n, \forall n \gt 1$?

Expanding $f(n)$ and $f(n-1)$, we get:

$$f(n)-f(n-1)=f\left(\left\lfloor\frac{2n-1}{3}\right\rfloor\right)+f\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)-f\left(\left\lfloor\frac{2n-3}{3}\right\rfloor\right)-f\left(\left\lfloor\frac{2n-2}{3}\right\rfloor\right)$$

Looking at the behaviour of the function given arguments modulo 3, we can see the following, $\forall n \gt 1$, where $D(n)=f(n)-f(n-1)$:

$$D(n)=\begin{cases} f\left(\left\lfloor\frac{2n-1}{3}\right\rfloor\right)+f\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)-f\left(\frac{2n}{3}-1\right)-f\left(\frac{2n-2}{3}\right) & \text{if}\space n\equiv1\pmod{3} \\ f\left(\left\lfloor\frac{2n-1}{3}\right\rfloor\right)+f\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)-f\left(\left\lfloor\frac{2n}{3}\right\rfloor-1\right)-f\left(\left\lfloor\frac{2n-2}{3}\right\rfloor\right) & \text{if}\space n\equiv2\pmod{3} \\ f\left(\frac{2n}{3}-1\right)+f\left(\frac{2n}{3}\right)-f\left(\left\lfloor\frac{2n}{3}\right\rfloor-1\right)-f\left(\left\lfloor\frac{2n-2}{3}\right\rfloor\right) & \text{if}\space n \equiv 0\pmod{3}\end{cases}$$

But I'm not sure how to construct a suitable counter example or proof of the proposition. A quick construction of the first 10 test cases, shows that $D(n)=1: n\equiv1\pmod{3}$, and $D(n)=1:n\equiv0\pmod{3}$.

However $D(2)=1$, $D(5)=2$ and $D(8)=4$, suggesting a power of 2 escalation, which would mean for sufficiently high $n:n\equiv2\pmod{3}$, $D(n)\gt n$, but I'm unsure how to show this.

Thanks in advance!

EDIT: Continuing my construction of the sequence has shown there is no power of 2 escalation, for successive terms $n\equiv2\pmod{3}$, however, as pointed out in the comments, all of the differences are powers of 2.

EDIT 2: If it helps anyone, by plotting a graph on Mathematica, I was able to determine that the assertion is false, with a counter example at $n=242$, with $f(242)=3072$, $f(241)=2816$, and therefore $f(242)-f(241)=256$, and as $256 \gt 242$, the assertion is false. But how could I disprove the assertion mathematically, without a computer?

Answer

I'm going to expand on the idea given by Leslie Townes in the comment above. Build a tree rooted in 2 on the integers $\ge 2$ with two types of edges:
$$2k\longrightarrow 3k\\
2k\longrightarrow 3k+1\\
2k+1\implies 3k+2$$
Then $\log_2 (f(n)-f(n-1))$ (which happens to be an integer) is the number of $\implies$ in the path from 2 to $n$.

We want a path with many $\implies$ and few $\longrightarrow$ (specifically, more than $\log_2 n$ $\implies$). Because exactly one of $3k$ and $3k+1$ is odd, there is a unique infinite path $P$ starting from 2 avoiding consecutive $\longrightarrow$. The density of $\implies$ in $P$ is at least $1/2$, and if it is higher than $\log_2 3/2$ we have succeeded.

I'm not sure if anything can be proven rigorously about the density of $P$ (the problem reminds me a bit of the Collatz conjecture so it could be difficult): if you do please comment.

But experimentally the density seems to be $2/3>\log_2 3/2$, so we are sure to find a counterexample that is a finite subpath of $P$ and indeed:

$$2\longrightarrow 3\implies 5\implies 8\longrightarrow 13\implies 20\longrightarrow 31\implies 47\implies 71\implies 107\implies 161\implies 242$$

There are 8 $\implies$ before 242, and $242<2^8$.