Functional equation: Show $0\le f(n+1)-f(n)\le 1$ and find all $n$ such that $f(n)=1025$.

Question

The function $f:\mathbb{N}\to \mathbb{R}$ satisfies all of

$$\begin{align}f(1)&=1, \\ f(2)&=2,\\ f(n + 2) &= f(n + 2 − f(n + 1)) + f(n + 1 − f(n)) \tag{1} \end{align}$$

Show that $0 \le f(n + 1) − f(n) \le 1 \tag{A}$

Find all $n$ for which $f(n) = 1025$.

This problem is taken from the 1986 Canada National Olympiad.

I believe that I have proven via strong induction that the function $f$ obeys a simpler recursion from which part (A) follows, but is there a simpler closed-form expression for $f(n)$, e.g. involving logs and floor functions? Is the proof okay?

---

Simplifying the Recursion

Computing a few more terms in the sequence:

$$\begin{align} n=1: &f(3)=f(3-f(2))+f(2-f(1))&=f(3-2)+f(2-1)&=2 \\ n=2: &f(4)=f(4-f(3))+f(3-f(2))&=f(4-2)+\color{blue}{f(3-2)}&=3 \\ n=3: &f(5)=f(5-f(4))+f(4-f(3))&=\color{blue}{f(5-3)}+f(4-2)&=4 \\ n=4: &f(6)=f(6-f(5))+f(5-f(4))&=\color{blue}{f(6-4)}+\color{blue}{f(5-3)}&=4 \\ n=5: &f(7)=f(7-f(6))+f(6-f(5))&=f(7-4)+\color{blue}{f(6-4)}&=4 \\ n=6: &f(8)=f(8-f(7))+f(7-f(6))&=f(8-4)+f(7-4)&=5 \\ n=7: &f(9)=f(9-f(8))+f(8-f(7))&=\color{blue}{f(9-5)}+f(8-4)&=6 \\ n=8: &f(10)=f(10-f(9))+f(9-f(8))&=\color{blue}{f(10-6)}+\color{blue}{f(9-5)}&=6 \\ n=9: &f(11)=f(11-f(10))+f(10-f(9))&=f(11-6)+\color{blue}{f(9-5)}&=7 \\ \end{align}$$

Function values are shown in blue when the corresponding function value in the line above has the same argument. This gives a simple guarantee that (A) is true. $f(8)$ is the first function value that does not have such a term when expanded. This avenue will not be pursued further.

Further values (not shown) lead me to conjecture that values are repeated as many times as the greatest power of 2 that divides the number ($2$ is repeated once, 4 twice, and odd numbers do not appear to be repeated); otherwise, values ascend by $1$. This will be tested via strong induction, and will lead to a simpler recursion formula.

To prove (A) formulate an Induction Hypothesis (IH) for positive integers $n$, suitable for use with strong induction.

1. For all integers $m\le n$ such that $m=2^q-1,q\ge1$, have $f(m)=2^{q-1}$
2. For all integers $m \le n$ such that $m=2^q,q\ge1$, have $f(m)=2^{q-1}+1$
3. For all other integers $m\le n$ express $m=2^q+r,r<2^q-1$, then $f(m)=2^{q-1}+f(r+1)$
4. For all $3\le m\le n$, have $1<f(m)<m$

The IH is clearly true for the base cases $n=1,n=2$.

When proving the inductive step by evaluating $f(n+1)$ via the recursion rule in (1), three cases must be considered.

Case 1: $n=2^q-2$ (IH.1 for $n+1$)

$$\begin{align} &f(n+1)\\ &=f(2^q-1)\\ &=f(2^q-1-f(2^q-2))+f(2^q-2-f(2^q-3)) \\ &=f(2^q-1-f(2^{q-1}+(2^{q-1}-2))) + f(2^q-2-f(2^{q-1}+(2^{q-1}-3))) \\ &=f(2^q-1-(2^{q-2}+f(2^{q-1}-1))) + f(2^q-2-(2^{q-2}+f(2^{q-1}-2)))&(\text{by IH.3}) \\ &=f(2^q-1-(2^{q-2}+2^{q-2}))) + f(2^q-2-(2^{q-2}+f(2^{q-1}-2)))&(\text{by IH.1}) \\ &=f(2^{q-1}-1) + f(2^q-2-(2^{q-2}+f(2^{q-2}+(2^{q-2}-2))))&(\text{algebra}) \\ &=2^{q-2} + f(2^q-2-(2^{q-2}+(2^{q-3}+f(2^{q-2}-1))))&(\text{IH.1, IH.3}) \\ &=2^{q-2} + f(2^q-2-(2^{q-2}+(2^{q-3}+2^{q-3})))&(\text{IH.1, IH.3}) \\ &=2^{q-2} + f(2^{q-2}+(2^{q-2}-2))&(\text{algebra}) \\ &=2^{q-2} + 2^{q-3}+f(2^{q-2}-1)&(\text{by IH.3}) \\ &=2^{q-2} + 2^{q-3}+ 2^{q-3} = 2^{q-1} &(\text{by IH.1}) \\ &\implies\text{IH.1 for }n+1=2^q-1 \end{align}$$

and $1 < 2^{q-1} < 2^q-1 \implies$ IH.4 for $n+1$.

Case 2: $n=2^q-1$ (IH.2 for $n+1$)

$$\begin{align} f(n+1)=f(2^q)&=f(2^q-f(2^q-1))+f(2^q-1-f(2^q-2)) \\ &=f(2^q-2^{q-1})+f(2^q-1-f(2^{q-1}+(2^{q-1}-2)) &(\text{by IH.1}) \\ &=f(2^{q-1})+f(2^q-1-(2^{q-2}+f(2^{q-1}-1)) &(\text{by IH.3}) \\ &=f(2^{q-1})+f(2^q-1-(2^{q-2}+2^{q-2})) &(\text{by IH.1}) \\ &=f(2^{q-1})+f(2^{q-1}-1) &(\text{simplifying}) \\ &=(2^{q-2}+1)+(2^{q-2}) &(\text{IH.1, IH.2}) \\ &=2^{q-1}+1 &(\text{simplifying}) \\ &\implies\text{IH.2 for }n+1=2^q \\ \end{align}$$

and $1 < 2^{q-1}+1 < 2^q \implies$ IH.4 for $n+1$.

Case 3a: $n=2^q$ (IH.3 for $n+1$)

$$\begin{align} f(n+1)=f(2^q+1)&=f(2^q+1-f(2^q))+f(2^q-f(2^q-1)) \\ &=f(2^q+1-(2^{q-1}+1))+f(2^q-(2^{q-1})) &(\text{by IH.1 and IH.2}) \\ &=2f(2^{q-1}) &(\text{simplifying}) \\ &=2(2^{q-2}+1) &(\text{by IH.2}) \\ &=2^{q-1}+2=2^{q-1}+f(2) &(\text{simplifying}) \\ &\implies\text{IH.3 for }n+1=2^q+1 \\ \end{align}$$

and $1 < 2^{q-1}+2 < 2^q+1 \implies$ IH.4 for $n+1$.

Case 3b: $n=2^q+1$ (IH.3 for $n+1$)

$$\begin{align} f(n+1)&=f(2^q+2)=f(2^q+2-f(2^q+1))+f(2^q+1-f(2^q)) \\ &=f(2^q+2-(2^{q-1}+f(2)))+f(2^q+1-(2^{q-1}+1)) &(\text{IH.3, IH.2}) \\ &=2f(2^{q-1}) &(\text{simplifying}) \\ &=2(2^{q-2}+1) &(\text{by IH.2}) \\ &=2^{q-1}+2=2^{q-1}+f(3) &(\text{simplifying}) \\ &\implies\text{IH.3 for }n+1=2^q+2 \\ \end{align}$$

and $1 < 2^{q-1}+2 < 2^q+2 \implies$ IH.4 for $n+1$.

Case 3c: $n=2^q+k,2\le k<2^q-1$ (IH.3 for $n+1$)

$$\begin{align} f(n+1)&=f(2^q+(k+1)) \\ &=f(2^q+k+1-f(2^q+k))+f(2^q+k-(2^q+k-1)) \\ &=f(2^q+k+1-(2^{q-1}+f(k+1)))+f(2^q+k-(2^{q-1}+f(k))) &(\text{by IH.3}) \\ &=f(2^{q-1}+k+1-f(k+1))+f(2^{q-1}+k-f(k)) &(\text{algebra}) \\ &=(2^{q-2}+f(k+2-f(k+1))) + (2^{q-2}+f(k+1-f(k))) &(\text{IH.4, IH.3}) \\ &=2^{q-1}+f(k+2-f(k+1))+f(k+1-f(k)) &(\text{algebra}) \\ &=2^{q-1}+f(k+2) &(\text{by (1)}) \\ &\implies\text{IH.3 for }n+1=2^q+(k+1) \\ \end{align}$$

and

$$\begin{align} &2^{q-1}+1 < 2^{q-1}+f(k+2) < 2^{q-1}+(k+2) &(\text{by IH.4 for k+2}) \\ &\implies 1 < 2^{q-1}+f(k+2) < 2^{q}+(k+1) \\ &\implies \text{IH.4 for }n+1 \end{align}$$

Result

This proves the induction hypothesis. Hence, ensuring agreement with the special cases for $n=1,n=2$, we have the following recursive definition for $f$:

$$f(n)=\begin{cases} 2^{q-1},&\text{ if }n=2^q-1, q\ge1 \\ 2^{q-1}+1,&\text{ else if } n=2^q, q\ge1 \\ 2^{q-1}+f(k+1),&\text{ else }n=2^q+k,1\le k<2^q-1,q\ge2 \end{cases}$$

This is equation (2) (I can't seem to place a label in-line).

Part (A)

If $n,n+1$ both fall into case 3 in equation (2), they can both be reduced without altering their difference. So eventually at least one of $n,n+1$ will reduce to either the form $2^q$ or $2^q-1$.

$$\begin{align} &\color{blue}{(n,n+1)\mapsto(2^q-2,2^q-1):} \\ f(n+1)-f(n)&=f(2^q-1)-f(2^q-2) \\ &=2^{q-1}-2^{q-1} &=0 \\\\ &\color{blue}{(n,n+1)\mapsto(2^q-1,2^q):} \\ f(n+1)-f(n)&=f(2^q)-f(2^q-1) \\ &=(2^{q-1}+1)-2^{q-1} &=1 \\\\ &\color{blue}{(n,n+1)\mapsto(2^q,2^q+1):} \\ f(n+1)-f(n)&=f(2^q+1)-f(2^q) \\ &=(2^{q-1}+f(2))-(2^{q-1}+1) &=1 \end{align}$$

Part (B)

By (2), we have:

$$\begin{align} f(2047)=f(2^{11}-1)=2^{10}=1024 < 1025 \\ f(2048)=f(2^{11})=2^{10}+1=1025 \\ f(2049)=f(2^{11}+1)=2^{10}+f(2)=1024+2=1026 > 1025 \end{align}$$

Since $f$ is non-descending, $n=2048$ is the unique solution to $f(n)=1025$.

Answer 1

Consider $g(k) = k + \lfloor \frac{k}{2^1} \rfloor + \lfloor \frac{k}{2^2} \rfloor + \lfloor \frac{k}{2^3} \rfloor + \ldots $, which is a strictly increasing sequence.

Claim: If $ g(k) \leq n < g(k+1)$, then $f(n) = k$.