Probar o refutar $f(n)-f(n-1)\le n, \forall n \gt 1$ para una función recursiva con pisos.

Question

La pregunta tipo olimpiada que se me planteó fue la siguiente:

Una función $f:\mathbb{N}\to\mathbb{N}$ se define por $f(1)=1$ y para $n>1$ , por: $$f(n)=f\left(\left\lfloor\frac{2n-1}{3}\right\rfloor\right)+f\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)$$ ¿Es cierto que $f(n)-f(n-1)\le n, \forall n \gt 1$ ?

Ampliar $f(n)$ y $f(n-1)$ obtenemos:

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

Observando el comportamiento de la función dados los argumentos módulo 3, podemos ver lo siguiente, $\forall n \gt 1$ , donde $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}$$

Pero no estoy seguro de cómo construir un contraejemplo adecuado o una prueba de la proposición. Una construcción rápida de los 10 primeros casos de prueba, muestra que $D(n)=1: n\equiv1\pmod{3}$ y $D(n)=1:n\equiv0\pmod{3}$ .

Sin embargo, $D(2)=1$ , $D(5)=2$ y $D(8)=4$ lo que sugiere una escalada de potencia 2, lo que significaría que para un nivel suficientemente alto $n:n\equiv2\pmod{3}$ , $D(n)\gt n$ pero no estoy seguro de cómo mostrarlo.

Gracias de antemano.

EDITAR : Siguiendo con mi construcción de la secuencia se ha demostrado que no hay escalada de potencia de 2, para términos sucesivos $n\equiv2\pmod{3}$ Sin embargo, como se señala en los comentarios, todas las diferencias son potencias de 2.

EDITAR 2 : Si le sirve a alguien, trazando un gráfico en Mathematica, pude determinar que la afirmación es falsa, con un contraejemplo en $n=242$ con $f(242)=3072$ , $f(241)=2816$ y por lo tanto $f(242)-f(241)=256$ y como $256 \gt 242$ la afirmación es falsa. Pero, ¿cómo podría refutar la afirmación matemáticamente, sin un ordenador?

Answer 1

Voy a ampliar la idea dada por Leslie Townes en el comentario anterior. Construir un árbol con raíz en 2 en los enteros $\ge 2$ con dos tipos de bordes: $$2k\longrightarrow 3k\\ 2k\longrightarrow 3k+1\\ 2k+1\implies 3k+2$$ Entonces $\log_2 (f(n)-f(n-1))$ (que resulta ser un número entero) es el número de $\implies$ en el camino de 2 a $n$ .

Queremos un camino con muchos $\implies$ y pocos $\longrightarrow$ (concretamente, más de $\log_2 n$ $\implies$ ). Porque exactamente uno de $3k$ y $3k+1$ es impar, hay un único camino infinito $P$ a partir de 2 evitando consecutivos $\longrightarrow$ . La densidad de $\implies$ en $P$ es al menos $1/2$ y si es superior a $\log_2 3/2$ lo hemos conseguido.

No estoy seguro de que se pueda demostrar algo con rigor sobre la densidad de $P$ (el problema me recuerda un poco a la conjetura de Collatz por lo que podría ser difícil): si lo haces por favor comenta.

Pero experimentalmente la densidad parece ser $2/3>\log_2 3/2$ por lo que estamos seguros de encontrar un contraejemplo que sea un subcamino finito de $P$ y de hecho:

$$2\longrightarrow 3\implies 5\implies 8\longrightarrow 13\implies 20\longrightarrow 31\implies 47\implies 71\implies 107\implies 161\implies 242$$

Hay 8 $\implies$ antes del 242, y $242<2^8$ .