Demostrar que $1\cdot f(1)+ 2\cdot f(2)+ ...+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ donde $f(n+1) = f(f(n))+1$

Question

Considere la posibilidad de la comprobación de la función $\mathbb{N}\to \mathbb{N}$ relación $f(n+1) = f(f(n))+1$, para cualquier entero positivo $n$. Demostrar que $1\cdot f(1)+ 2\cdot f(2)+ ...+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ para cualquier entero positivo $n$.

Answer 1

voy a intentar. la definición de la relación de $f$ nos da la desigualdad $$nf(n) = n\{f(f(n-1)) + 1\} =n + nf(f(n-1)) \ge n $$ because the range of $f$ consiste en los enteros positivos. podemos usar $jf(j) \ge j$ nuevo y de nuevo para obtener $$ nf(n) \ge n + nf(f(n-1)) \ge n + nf(n-1) \ge n + n(n-1) = n^2$$

por lo tanto

$$1f(1) + 2f(2) + \cdots + nf(n) \ge 1^2 + 2^2 + \cdots + n^2 = n(n+1)(2n+1)/6 $$

${\bf edit}:$ el argumento utilizado para establecer $f(n) \ge n$ tiene un fallo, pero no la conclusión y que puede ser fijo.

ya tenemos $f(n) \ge 1 \text{ for all } n \ge 1$ en el rango de $f$ ser enteros positivos. usando ahora que e $f(n) = f(f(n-1) + 1$ establece $f(n) \ge 2 \text{ for } n \ge 2 $. ahora por inducción $f(n) \ge n.$

Answer 2

Si $f(x)=f(y)$$f(x+1)=f(f(x))+1=f(f(y))+1=f(y+1)$, lo $f(n)$ es periódica. Pero cada número $f(m)$ en el ciclo es uno más que otro número en el ciclo. Esto es una contradicción, por lo $f(x)\neq f(y)$ al $x\neq y$.
$f(n+1)=f(f(n))+1>f(f(n))$, lo $f(n+1)$ nunca es el valor más bajo que el $f(x)$ toma. Por lo $f(1)$ debe ser el valor más bajo que el $f(x)$ toma.
Si $m=f(n)$ $f$- valor, otros de $f(1)$, $m-1=f(n)-1=f(f(n-1))$ $f$- valor. De la misma manera, $m-2$ es así, todo el camino hacia abajo a $f(1)$.
Por lo $f(1)+1$ $f$- valor, se $f(1)+1=f(k+1)=f(f(k))+1$, lo $f(1)=f(f(k))$, e $1=f(k)$. Este es el valor más bajo posible para $f$, lo $k=1$.
Por lo $f(1)=1$, y por inducción, $f(n)=n$.

Answer 3

Desde $1\cdot 1+ 2\cdot 2+ \cdots + n\cdot n = n(n+1)(2n+1)/6$, es suficiente para probar que $f(n)\le n$, para todos los $n$.

Vamos a demostrar que $f(n)\le n$ todos los $n$, por inducción completa.

Suponga $f(m)\le m$ todos los $m\le n$. Vamos a demostrar que $f(n+1) \le n+1$.

Deje $m=f(n) \le n$. A continuación,$f(f(n))=f(m) \le m=f(n)$.

Por eso, $f(n+1) = f(f(n))+1 \le f(n)+1 \le n+1$.

Todo lo que queda es la base de la inducción: $f(1)\le 1$.