Let's solve the problem, which is still unsolved: We know that all the unknowns are integers, so the smallest one must greater or equal to 1. Let me denote the permutations of $(k_1,k_2,...,k_n)$ with $(y_1,y_2,...,y_n)=y_i (*)$. From the rearrangement's inequality we know that $Random Sum\geq Reversed Sum$. We will denote we permutations of $y_i$ in this form $y_n \geq ...\geq y_1$. So we have $\frac{k_1}{1^2}+\frac{k_2}{2^2}+...+\frac{k_n}{n^2} \geq \frac{y_1}{1^2}+ \frac{y_2}{2^2}+...+ \frac{y_n}{n^2} \geq 1+\frac{1}{2}+...+\frac{1}{n}$. Let's denote $\frac{y_1}{1^2}+ \frac{y_2}{2^2}+...+ \frac{y_n}{n^2}=T$ and $1+\frac{1}{2}+...+\frac{1}{n}=S$. We have $T \geq S$. Which comes from $y_1 \geq1, y_2 \geq2, ...,y_n \geq n$. So we are done.

It is easy proved by induktion. Let $f_0(x)=f(x)$ and $f_i(x)=f_{i-1}(x)$ if $f_{i-1}(i)=i$, else exist k>i $f_{i-1}(k)=i,f_{i-1}(i)=m>i$ we denote $f_i(x)=f_{i-1}(x),x\not=k,i, f_i(i)=i,f_i(k)=m$. Let \[ S_n(f)=\sum_{k=1}^n \frac{f(k)}{k^2} \]. It is easy to show, that $S_n(f_i)\ge S(f_{i+1})$.

We just have to use the Rearrangement Inequality.

orl wrote: Let $ f$ be an injective function from $ {1,2,3,\ldots}$ in itself. Prove that for any $ n$ we have: $ \sum_{k = 1}^{n} f(k)k^{ - 2} \geq \sum_{k = 1}^{n} k^{ - 1}.$ Let $ f(k)=a_k$, where $ a_k \in \{1,2,3,...\}=\mathbb{N}$. \[ \sum_{k=1}^{n} f(k)k^-2 =\sum_{k=1}^n {\frac{a_k}{k^2}} \geq \sum_{k=1}^{n}{\frac{1}{k}}\] By AM-GM, for each $ k\in \mathbb {N}$ we have: \[ \frac{a_k}{k^2} +\frac{1}{a_k} \geq \frac{2}{k}\] \[ \implies \sum_{k=1} ^n {\frac{a_k}{k^2}} +\sum_{k=1}^n {\frac{1}{a_k}} \geq 2\sum_{k=1}^n {\frac{1 }{k}}\] Therefore, it is enough to prove that: \[ \frac{1}{1} +\frac{1}{2} +... +\frac{1}{n} \geq \frac{1}{a_1} +\frac{1}{a_2} +...+\frac{1}{a_n}\] But this is obviously true because all $ a_i$ numbers are different natural numbers.

Very simple question. The only trick is in realising that the rearrangement inequality can be used and then seeing that positive integers are greater than 1.

lemma $\sum_{r=1}^{n} x_r y_r =X_n y_n -\sum_{r=1}^{n-1}X_{r} (y_{r+1} -y_r)$ where $X_r= x_1+x_2+\cdots+x_r$ The proof is trivial and it is kind of integration by parts. Let, $F(k)=\sum_{k=1}^{k} f(k) \ge \frac{k(k+1)}{2}$.so from the lemma we get, \begin{align*} \sum_{k=1}^{n} \frac{f(k)}{k^{2}}& = \frac{F(n)}{n^{2}} -\sum_{k=1}^{n-1} F(n-1) \left(\frac{1}{(k+1)^2} -\frac{1}{k^2}\right)\\ & \ge \frac{n+1}{2n} -\sum_{k=1}^{n-1} \frac{k(k+1)}{2}. \frac{-(2k+1)}{k^2(k+1)^2}\\ & =\frac{n+1}{2n} +\frac{1}{2}\sum_{k=1}^{n-1} \frac{2k+1}{k(k+1)}\\ & =\frac{1}{2}+\frac{1}{2n}+\frac{1}{2} \sum_{k=1}^{n-1} \left(\frac{1}{k}+ \frac{1}{k+1}\right)\\ & = \frac{1}{2} \left(\sum_{k=1}^{n} \frac{1}{k} +\sum_{k=0}^{n-1} \frac{1}{k+1}\right)\\ & = \sum_{k=1}^{n} \frac{1}{k} \end{align*}

Hmmm ... your lemma is just Abel's summation formula. Let's call a rabbit a rabbit.

orl wrote: Let $f$ be an injective function from ${1,2,3,\ldots}$ in itself. Prove that for any $n$ we have: $\sum_{k=1}^{n} f(k)k^{-2} \geq \sum_{k=1}^{n} k^{-1}.$ Assume to sequence $f(x_1),f(x_2),\cdots,f(x_k)$ where $x_k$'s are the permutation of $\{1,2,\cdots,n\}$ and $\left\{\frac{1}{k^2}\right\}$.They are similar.So applying chebyshev inequality, \begin{align*}\sum_{k=1}^{n} \frac{f(k)}{k^2}& \ge \frac{1}{n} \sum_{k=1}^{n} f(k). \sum_{k=1}^{n} \frac{1}{k^2}\\ & \ge \frac{1}{n}.\frac{n(n+1)}{2}. \frac{1}{n} \left(\sum_{k=1}^{n} \frac{1}{k}\right)^{2}\\ & \ge \frac{n(n+1)}{2n^2}.\sum_{k=1}^{n}\frac{1}{k}.\frac{n^2}{1+2+\cdots+n}\\ & \ge \sum_{k=1}^{n}\frac{1}{k}\end{align*}

Also we can use: $\frac{f(k)}{k^2}\geq \frac{2}{k}-\frac{1}{f(k)}$

Let $a_1,a_2,\dots,a_n$ be a sequence of distinct positive integers such that $f(i)=a_i$. Note that $\sum\limits_{k=1}^n a_k^{-1}\le\sum\limits_{k=1}^n k^{-1}$ since all $a_k$ are distinct positive integers. Cauchy Schwarz yields \[\left(\sum\limits_{k=1}^n a_k^{-1}\right)\left(\sum\limits_{k=1}^n a_k k^{-2}\right)\ge\left(\sum\limits_{k=1}^nk^{-1}\right)^2.\] Dividing by $\sum\limits_{k=1}^n a_k^{-1}$ yields \[\sum\limits_{k=1}^n a_k k^{-2}\ge\frac{\left(\sum\limits_{k=1}^nk^{-1}\right)\left(\sum\limits_{k=1}^nk^{-1}\right)}{\sum\limits_{k=1}^n a_k^{-1}}\implies \sum\limits_{k=1}^n a_k k^{-2}\ge\left(\sum\limits_{k=1}^nk^{-1}\right)\cdot\frac{\left(\sum\limits_{k=1}^nk^{-1}\right)}{\sum\limits_{k=1}^n a_k^{-1}}.\] Since $\sum\limits_{k=1}^n a_k^{-1}\le\sum\limits_{k=1}^n k^{-1}$, then $\frac{\left(\sum\limits_{k=1}^nk^{-1}\right)}{\sum\limits_{k=1}^n a_k^{-1}}\ge 1$. Thus, we have $\sum\limits_{k=1}^n a_k k^{-2}\ge\sum\limits_{k=1}^nk^{-1}$ as desired.

We can simply put the R.H.S as $1/k$ to $k/k^2$ and use rearrangement inequality it's done in like two lines. The R.H.S is a scalar product of two sequences sorted in the opposite way. The R.H.S is a scalar product of rearranged sequences. Q.E.D

What's an injective function?

al_wang wrote: What's an injective function? Let's say there is a function going from $X->Y$ Then, imagine arrows flying from the $X$ to $Y$ It's an injective function when the arrow from Xs is shot at different Ys, which mean than one Y cannot be shot two times Thus, if $f(x1)$ is unequal to $f(x2)$, then also $x1$ and $x2$ is different

Sorry for reviving this thread, but couldn't resist posting my solution to this problem. Solution Clearly $f$ being injective implies that: $\sum \dfrac{f(k)}{k^2} = \sum \dfrac {a_k}{k^2} $ where $a_k = f(k) $. Thus, the inequality to prove is : $ \sum \dfrac {a_k}{k^2} \ge \sum \dfrac {1}{k^2} $ Now consider a permutation $(b_1,b_2, \dots , b_n)$ of ${a_k}$ such that $b_i \le b_j \forall i \le j $ Therefore by rearrangement inequality $ \sum \dfrac {a_k}{k^2} \ge\sum \dfrac {b_k}{k^2}$ Claim: $\sum \dfrac{b_k}{k^2} \ge \sum \dfrac {1}{k^2} $ Proof: this is trivial since $ b_1 < b_2 < \dots < b_n$ and $b_1 \ge 1 $ Thus, $b_k \ge k$ for any $ k \in { 1,2,\dots,n} $

Electron_Madnesss wrote: Proof: this is trivial since $ b_1 \le b_2 \le \dots \le b_n$ and $b_1 \ge 1 $ It should be $< $, not $\leq $, but other than that good formalisation. This is the easiest IMO I have ever seen! It's just Rearrangement.

We may use induction as well. If for all permutations of $S=\{1,2,...,n\}$ we have the inequality is satisfied then we can show that for all permutations of $S_1=S\cup\{n+1\}$ it will be satisfied. Let, $\sigma_{f,n}=\sum_{k=1}^{n}\frac{f(k)}{k^2}\geq \sum_{k=1}^n \frac{1}{k}=\sigma_{0}(n)$ for all bijective functions $f:S\rightarrow S$. So, $\sigma_{f,n}+\frac{n+1}{(n+1)^2}\geq \sigma_{0}(n+1)$ Now, we interchange any $f(k)$ with $n+1$. $\sigma_{f,n}$ will be changed by $\Delta=(n+1-f(k))(\frac{1}{k^2}-\frac{1}{(n+1)^2}) >0$ as $f(k)<n+1$. Hence, $\sigma_{f,n+1}\geq \sigma_{0}(n+1)$. As, the inequality is true for all permutations for $n=2$, ($\sigma_{f,2}=\{9/4, 3/2\}$ and $\sigma_{0}(2)=3/2$ ) so is true for all $n$.

Let $(b_1,b_2,\ldots,b_n)$ be the permutation of $(a_1,a_2,\ldots,a_n)$ such that $b_1\le b_2\le\ldots\le b_n$. Thus by the rearrangement inequality we get that $$\sum_{k=1}^{n}\frac{a_k}{k^2}\ge\sum_{k=1}^{n}\frac{b_k}{k^2}$$Clearly $b_1\ge 1,b_2\ge 2,\ldots,b_n\ge n$, so $$\sum_{k=1}^{n}\frac{b_k}{k^2}\ge\sum_{k=1}^{n}\frac{k}{k^2}=\sum_{k=1}^{n}\frac{1}{k}$$