Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
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

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.