$f:\mathbb Z^+\to\mathbb Z^+$ satisfying $f(n+1)\in\{4f(n)-1,f(n)-1\}$, with a unique $n\in\mathbb Z^+$ such that $f(n)=m$ for all $m\in\mathbb Z^+$

Question

This is functional equation problem from BMO 1999 Q5. The question states:

Consider all functions $ f $ from the positive integers to the positive integers such that

(i) for each positive integer $ m $, there is a unique positive integer $ n $ such that $ f ( n ) = m $ (i.e. the function is onto).

(ii) for each positive integer $n$, we have $f(n + 1)$ is either: $$ 4 f ( n ) - 1$$ or $$ f ( n ) - 1 \text . $$

Find the set of positive integers $ p $ such that $ f ( 1999 ) = p $ for some function $ f $ with properties (i) and (ii).

How do I start this question. I can see that $ 4 f ( n ) - 1 $ is always odd. I've also tried plugging in some values after letting $ f ( n + 1 ) = f ( n ) - 1 $ but that hasn't really helped me find an opening.

Solutions focused on how to think through the question will be most appreciated!

Answer 1

When I look at this question, the first thing that stands out is that being bijective (as noted in a comment, the condition is much stronger than being onto) is a very strong condition — so strong that it's an interesting starting point for exploration. For instance, there's some unique $m$ with $f(m)=1$. Now, what can this $m$ be? Well, either $1$ was our initial value (i.e. $f(1)=1$) — and I'll come back to that case in a bit — or else we have $f(m-1)=2$. Now, suppose that this isn't the initial value of $f()$; then we have to have had $f(m-2)=3$. But I also know that $f(m+1)$ will be equal to $4f(m)-1=4\cdot1-1=3$, so this is a contradiction; it must be the case that either $f(1)=1$ or $f(1)=2, f(2)=1$.

More generally, suppose I take some 'forward step' $f(m+1)=4f(m)-1$ and that I've already accounted for all the values $\leq f(m)$. Then how can I get all the values that are less than $f(m+1)$? They can't be generated 'from below', because I'd have to go back to a value I've already generated (contradicting the conditions of the problem); this means they must be generated 'from above'. But this then locks in a stretch of values of $f()$ — can you see why? And by iterating this process, the entire question is answered.