# $a_n=\frac{1}{n}\left(\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+...+\left[\frac{n}{n}\right]\right)$, $a_{n+1}>a_n$

Let $[x]$ denote the greatest integer less than or equal to the real number $x$.

Consider the sequence $a1, a2, . . .$ defined by

$a_n=\frac{1}{n}\left(\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+...+\left[\frac{n}{n}\right]\right)$, $n\in N^*$

Prove that $a_{n+1} > a_n$ for infinitely many n, and determine whether $a_{n+1} < a_n$ for infinitely many $n$.

## I've done:

$\left[\frac{n+1}{1}\right]+\left[\frac{n+1}{2}\right]+...+\left[\frac{n+1}{n+1}\right]<\frac{n+1}{1}+\frac{n+1}{2}+...+\frac{n+1}{n+1}$

$\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+...+\left[\frac{n}{n}\right]<\frac{n}{1}+\frac{n}{2}+...+\frac{n}{n}$

## And

$\frac{1}{n+1}(\left[\frac{n+1}{1}\right]+\left[\frac{n+1}{2}\right]+...+\left[\frac{n+1}{n+1}\right])<\frac{1}{n+1}(\frac{n+1}{1}+\frac{n+1}{2}+...+\frac{n+1}{n+1})$

$\frac{1}{n}(\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+...+\left[\frac{n}{n}\right])<\frac{1}{n}(\frac{n}{1}+\frac{n}{2}+...+\frac{n}{n})$

## So

$\frac{1}{n+1}(\left[\frac{n+1}{1}\right]+\left[\frac{n+1}{2}\right]+...+\left[\frac{n+1}{n+1}\right])<(\frac{1}{1}+\frac{1}{2}+...+\frac{1}{n+1})$

$\frac{1}{n}(\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+...+\left[\frac{n}{n}\right])<(\frac{1}{1}+\frac{1}{2}+...+\frac{1}{n})$

$a_{n+1}<\frac{1}{1}+\frac{1}{2}+...+\frac{1}{n+1}$

$a_n<\frac{1}{1}+\frac{1}{2}+...+\frac{1}{n}$

And kind of stopped here... Could I have some hints on how to get this done? And looking at the task, if I prove $a_{n+1}>a_n$ is it possible to be the other way around as well as the second part of the task asks me to verify? Thank you.

• From your result, as ${n\to \infty}$, $a_n \to a_{n+1}$, but always from left hand side. Also $a_{n+1} < a_n$ is not possible as you already have shown the opposite to be true. Commented Aug 26, 2017 at 16:11
• Just noticed my result was wrong, as I couldn't subtract one inequality from the other... @akhmeteni Commented Aug 26, 2017 at 16:16
• See here. Commented Aug 26, 2017 at 16:21
• Thank you. I've looked for it there as well, but I guess I should've looked for longer. @shrimpabcdefg Commented Aug 26, 2017 at 16:24
• If $d(k)$ is the number of divisor of $k$ then $a_{n+1}>a_n$ if $d(n+1)\ge d(n)$ and vice versa Commented Aug 26, 2017 at 17:58

Say $f(n)=\left[\frac{n}{1}\right]+\left[\frac{n}{2}\right]+...+\left[\frac{n}{n}\right]$, then

$$f(n+1)-f(n)=1+\sum_{k=1}^n\left(\left[\frac{n+1}{k}\right]-\left[\frac{n}{k}\right]\right)=\#\text{positive divisors of n+1}=\sigma(n+1)$$

(Define $\sigma(n)=$ number of positive divisors of n)

Then by using inductive hypothesis and $f(1)=1$,

$$f(n)=\sigma(1)+\sigma(2)+\cdots+\sigma(n)$$

and we know $a_n=\dfrac{f(n)}{n}$

$$\Rightarrow a_{n+1}-a_n=\dfrac{f(n+1)}{n+1}-\dfrac{f(n)}{n}=\dfrac{f(n)+\sigma(n+1)}{n+1}-\dfrac{f(n)}{n}=\dfrac{n*\sigma(n+1)-f(n)}{n(n+1)}$$

$$=\dfrac{n*\sigma(n+1)-(\sigma(1)+\sigma(2)+\cdots+\sigma(n))}{n(n+1)}$$

$$=\dfrac{\left[(\sigma(n+1)-\sigma(1)\right]+\left[\sigma(n+1)-\sigma(2)\right]+\cdots+\left[\sigma(n+1)-\sigma(n)\right]}{n(n+1)}$$

If we can choose $n$ such that $\sigma(n+1)\gt\sigma(k)$ for all $k=1,2,...,n$, then we get $a_{n+1}\gt a_n$.

Let's analyze the sigma function:

$$\*\sigma(1)=1,\qquad\*\sigma(2)=2,\qquad\sigma(3)=2,\qquad\*\sigma(4)=3,\qquad\sigma(5)=2$$ $$\*\sigma(6)=4,\qquad\sigma(7)=2,\qquad\sigma(8)=4,\qquad\sigma(9)=3,\qquad\sigma(10)=4$$ $$\sigma(11)=2,\qquad\*\sigma(12)=6,\qquad\sigma(13)=2,\qquad\sigma(14)=4,\qquad\sigma(15)=4$$

It's obvious that $\sigma(n)$ goes to infinity (because $\sigma(2^k)=k+1$)

By this fact and above table we see that for all $t\gt 0$, there is always minimum $n\geq t$ satisfying $\sigma(n+1)\gt \max(\sigma(1),...,\sigma(t))$ which means $\sigma(n+1)\gt \max(\sigma(1),...,\sigma(n))$ because of the minimality of $n$. I identify such $n+1$'s in the table and these make $a_{n+1}$ greater than $a_{n}$.