<s>[INST] Prove that $\sum_{i=1}^{n} \frac{n+i}{i+1} \le 1 + n(n-1) \ \forall n \in \Bbb{N}$ (without calculus) I'm trying to prove the following proposition (I'm not supposed to use calculus):
$$\sum_{i=1}^{n} \frac{n+i}{i+1} \le 1 + n(n-1) \ \forall n \in \Bbb{N}$$
(I'm assuming that $0 \notin \Bbb{N}$)
This is what I've tried so far:
$\sum_{i=1}^{n} \frac{n+i}{i+1} = \sum_{i=1}^{n}[ \frac{n}{i+1} + \frac{i}{i+1} ] = [\sum_{i=1}^{n} \frac{n}{i+1}] + \sum_{i=1}^{n} \frac{i}{i+1} = n[\sum_{i=1}^{n} \frac{1}{i+1}] + \sum_{i=1}^{n} \frac{i}{i+1}$
Let $j= i +1$ . So now we have:
$\sum_{i=1}^{n} \frac{n+i}{i+1} =  n[\sum_{j=2}^{n+1} \frac{1}{j}] + \sum_{j=2}^{n+1} \frac{j-1}{j}$
$= n[\sum_{j=2}^{n+1} \frac{1}{j}]  + \sum_{j=2}^{n+1} \frac{j}{j} - \sum_{j=2}^{n+1} \frac{1}{j}$
$= n[\sum_{j=2}^{n+1} \frac{1}{j}]- \sum_{j=2}^{n+1} \frac{1}{j} + \sum_{j=2}^{n+1} 1 $
$= (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] + [\sum_{j=1}^{n+1} 1 ] -1 $
$= (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] + n+1 -1 $
$= (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] + n$
Therefore proving the following inequality is the same as proving the original:
$$ (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] + n \le 1 + n(n-1)$$
If $n=1$ then $ (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] + n = 1$ and $1 + n(n-1) = 1$
Now I assume that $n>1$:
$ (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] + n \le 1 + n(n-1) \iff  (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] + n \le 1 + n^2 - n$
$\iff (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] \le 1 + n^2 - 2n$
$\iff (n-1)[\sum_{j=2}^{n+1} \frac{1}{j}] \le (n-1)^2$
$\iff \sum_{j=2}^{n+1} \frac{1}{j} \le \frac{(n-1)^2}{n-1}$
$\iff \sum_{j=2}^{n+1} \frac{1}{j} \le n-1$
$\iff 1 + \sum_{j=2}^{n+1} \frac{1}{j} \le n$
$\iff \sum_{j=1}^{n+1} \frac{1}{j} \le n$
And here is where I'm stuck. I know that an upper bound for the harmonic sum can be found using an integral test but I'm not supposed to use calculus. Is there a discrete way of proving that $\sum_{j=1}^{n+1} \frac{1}{j} \le n$ for all natural $n \ge 2$ ? Or maybe another way of proving the proposition without ending up with the harmonic sum?
 [/INST] You can use $$\frac{1}{j} \le \frac 12 ~ \forall j \ge 2$$
Therefore $$\sum_{j=2}^{n+1}\frac 1j \le n \times \left(\frac{1}{2}\right) \implies \color{blue}{1} +\sum_{j=2}^{n+1}\frac 1j \le \frac{n+2}{2} \le n \quad \forall \;n \ge 2$$
For, $n=1$ it is easy to verify, that it's incorrect.
</s>