# 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.

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?

-
Reference: problem 2 in round 2 of the British Mathematical Olympiad, January 2012 (bmoc.maths.org/home/bmo2-2012.pdf). It may be useful to notice/prove that the sequence $d(n) = f(n) - f(n-1)$ satisfies $d(2) = 1$, $d(3k) = d(3k+1) = d(2k)$, and $d(3k+2) = 2 d(2k+1)$ for all $k \geq 1$. This allows $d(n)$ to be rapidly computed (and shows quite clearly that $d(n)$ is always a power of $2$). The sequence of $n$ for which $d(n) > n$ is in the OEIS: oeis.org/A205594 – leslie townes Jun 14 '12 at 7:17

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$.

-
Ahh, great solution! I'm slightly lost as to why $D(n)\gt n$, when the density of $\implies$ in $P$ is greater than $\log_{2}{\frac{3}{2}}$ though? Thanks! – Shaktal Jun 14 '12 at 15:23
The elements $n_k$ in the sequence grow as $\Theta\left((3/2)^k\right)$, so if the density of $\implies$ in long enough prefixes of $P$ exceeds $q>\log_2 \frac 3 2$, $d(n_k)$ grows as $\Omega(q^k)$ and will end up exceeding $n_k$ for large enough $k$. – Generic Human Jun 14 '12 at 15:42
That's cleared that up, your solution is remarkably simple and elegant then! Thanks a lot (I'd +2 if I could)! – Shaktal Jun 14 '12 at 15:43
You're welcome :-) FYI, I opened a question about the asymptotic density: math.stackexchange.com/questions/158293/… – Generic Human Jun 14 '12 at 15:54