Prove that $1\cdot f(1)+ 2\cdot f(2)+ ...+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ where $f(n+1) = f(f(n))+1$

Question

Consider checking function $\mathbb{N}\to \mathbb{N}$ relationship $f(n+1) = f(f(n))+1$, for any positive integer $n$. Prove that $1\cdot f(1)+ 2\cdot f(2)+ ...+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ for any positive integer $n$.

Answer 1

i am going to try. the defining relation for $f$ gives us the inequality $$nf(n) = n\{f(f(n-1)) + 1\} =n + nf(f(n-1)) \ge n $$ because the range of $f$ consists of positive integers. we can use $jf(j) \ge j$ again and again to get $$ nf(n) \ge n + nf(f(n-1)) \ge n + nf(n-1) \ge n + n(n-1) = n^2$$

therefore

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

${\bf edit}:$ the argument used to establish $f(n) \ge n$ has a flaw but not the conclusion and it can be fixed.

we already have $f(n) \ge 1 \text{ for all } n \ge 1$ by the range of $f$ being positive integers. now using that and $f(n) = f(f(n-1) + 1$ establishes $f(n) \ge 2 \text{ for } n \ge 2 $. now by induction $f(n) \ge n.$

Answer 2

If $f(x)=f(y)$ then $f(x+1)=f(f(x))+1=f(f(y))+1=f(y+1)$, so $f(n)$ is periodic. But every number $f(m)$ in the cycle is one more than another number in the cycle. This is a contradiction, so $f(x)\neq f(y)$ when $x\neq y$.
$f(n+1)=f(f(n))+1>f(f(n))$, so $f(n+1)$ is never the lowest value that $f(x)$ takes. So $f(1)$ must be the lowest value that $f(x)$ takes.
If $m=f(n)$ is an $f$-value, other than $f(1)$, then $m-1=f(n)-1=f(f(n-1))$ is also an $f$-value. In the same way, $m-2$ is as well, all the way down to $f(1)$.
So $f(1)+1$ is an $f$-value, call it $f(1)+1=f(k+1)=f(f(k))+1$, so $f(1)=f(f(k))$, and $1=f(k)$. This is the lowest possible value for $f$, so $k=1$.
So $f(1)=1$, and by induction, $f(n)=n$.

Answer 3

Since $1\cdot 1+ 2\cdot 2+ \cdots + n\cdot n = n(n+1)(2n+1)/6$, it is enough to prove that $f(n)\le n$, for all $n$.

We shall prove that $f(n)\le n$ for all $n$, by full induction.

Assume $f(m)\le m$ for all $m\le n$. Let's prove that $f(n+1) \le n+1$.

Let $m=f(n) \le n$. Then $f(f(n))=f(m) \le m=f(n)$.

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

All that remains is the base of induction: $f(1)\le 1$.