$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$

Question

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.

Answer 1

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}$.