7
$\begingroup$

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?

  • 6
    Reference: problem$2$in round 2 of the British Mathematical Olympiad, January 2012 (http://www.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: http://oeis.org/A2055942012-06-14

1 Answers 1

6

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

  • 0
    You're welcome :-) FYI, I opened a question about the asymptotic density: http://math.stackexchange.com/questions/158293/density-of-odd-numbers-in-a-sequence-relating-base-2-and-base-3-expansion2012-06-14