Ecuación funcional: Mostrar $0\le f(n+1)-f(n)\le 1$ y encontrar todos $n$ tal que $f(n)=1025$ .

Question

La función $f:\mathbb{N}\to \mathbb{R}$ satisface todas

$$\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}$$

Demuestre que $0 \le f(n + 1) f(n) \le 1 \tag{A}$

Buscar todos $n$ para lo cual $f(n) = 1025$ .

Este problema procede de la Olimpiada Nacional de Canadá de 1986.

Creo que he demostrado por inducción fuerte que la función $f$ obedece a una recursión más sencilla de la que se deduce la parte (A), pero ¿existe una expresión de forma cerrada más sencilla para $f(n)$ por ejemplo, ¿con funciones logarítmicas y de suelo? ¿Está bien la prueba?

---

Simplificar la recursión

Computar algunos términos más en la secuencia:

$$\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}$$

Los valores de función se muestran en azul cuando el valor de función correspondiente en la línea anterior tiene el mismo argumento. Esto ofrece una garantía sencilla de que (A) es cierta. $f(8)$ es el primer valor de la función que no tiene dicho término cuando se expande. No se seguirá por esta vía.

Otros valores (no mostrados) me llevan a conjeturar que los valores se repiten tantas veces como la mayor potencia de 2 que divide al número ( $2$ se repite una vez, 4 dos veces, y los números impar no parecen repetirse); de lo contrario, los valores ascienden por $1$ . Esto se probará mediante inducción fuerte, y conducirá a una fórmula de recursión más simple.

Para demostrar (A) formule una Hipótesis de Inducción (IH) para enteros positivos $n$ , adecuado para su uso con inducción fuerte.

1. Para todos los números enteros $m\le n$ tal que $m=2^q-1,q\ge1$ , han $f(m)=2^{q-1}$
2. Para todos los números enteros $m \le n$ tal que $m=2^q,q\ge1$ , han $f(m)=2^{q-1}+1$
3. Para todos los demás números enteros $m\le n$ express $m=2^q+r,r<2^q-1$ alors $f(m)=2^{q-1}+f(r+1)$
4. Para todos $3\le m\le n$ , han $1<f(m)<m$

El IH es claramente cierto para los casos base $n=1,n=2$ .

Al probar el paso inductivo evaluando $f(n+1)$ mediante la regla de recursión de (1), hay que considerar tres casos.

Caso 1: $n=2^q-2$ (IH.1 para $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}$$

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

Caso 2: $n=2^q-1$ (IH.2 para $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}$$

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

Caso 3a: $n=2^q$ (IH.3 para $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}$$

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

Caso 3b: $n=2^q+1$ (IH.3 para $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}$$

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

Caso 3c: $n=2^q+k,2\le k<2^q-1$ (IH.3 para $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}$$

y

$$\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}$$

Resultado

Esto demuestra la hipótesis de inducción. Por lo tanto, garantizando la concordancia con los casos especiales para $n=1,n=2$ tenemos la siguiente definición recursiva para $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}$$

Esta es la ecuación (2) (no consigo colocar una etiqueta en línea).

Parte (A)

Si $n,n+1$ ambos entran en el caso 3 de la ecuación (2), ambos pueden reducirse sin alterar su diferencia. Así que, al final, al menos uno de $n,n+1$ se reducirá a la forma $2^q$ o $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}$$

Parte (B)

Por (2), tenemos:

$$\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}$$

Desde $f$ no es descendente, $n=2048$ es la única solución de $f(n)=1025$ .

Answer 1

Considere $g(k) = k + \lfloor \frac{k}{2^1} \rfloor + \lfloor \frac{k}{2^2} \rfloor + \lfloor \frac{k}{2^3} \rfloor + \ldots $ que es una secuencia estrictamente creciente.

Alegación: Si $ g(k) \leq n < g(k+1)$ alors $f(n) = k$ .