Prove that there exist infinitely many $n$ such that $d(n+1)>d(n)$, where $d(n)$ is number of positive factors

Question

Prove that there exist infinitely many $n$ such that $d(n+1)>d(n)$, where $d(n)$ is number of positive factors of $n$.

I have think of using proof by contradiction, by setting a largest integer $k$ such that $d(k+1)>d(k)$. Does anyone has any idea or hints?

Answer 1

The number of divisors of $2^n$ is $n+1$, so the number of divisors can become arbitary large. If from some point on , $d(n+1)\le d(n)$ would always hold, the number of divisors would be bounded for all positive integers. This is a contradiction.

Answer 2

I have think of using proof by contradiction, by setting a largest integer $k$ such that $d(k+1)>d(k)$.

This approach is good, and will work. Let's continue it. So $k$ is the largest integer such that $d(k+1) > d(k)$. What does that mean about $d(k+1)$, $d(k+2)$, $d(k+3)$, and so on? Well, it means that

• $d(k+2)$ is NOT larger than $d(k+1)$, that is, $d(k+2) \le d(k+1)$;

• $d(k+3)$ is NOT larger than $d(k+2)$, that is, $d(k+3) \le d(k+2)$;

and so on. So we conclude that $$ d(k+1) \ge d(k+2) \ge d(k+3) \ge d(k+4) \ge d(k+5) \ge \cdots $$ and so on.

What this means is that $d(n)$ is "weakly decreasing" for $n > k$, or in simpler terms, $d(n)$ never gets larger than $d(k)$.

So to get a contradiction, we should come up with some $n$ such that $d(n)$ keeps getting larger and larger. Peter's answer gives one idea: $n$ is a power of two $(n = 2^m$). Another idea would be to consider $$ n = p_1 p_2 p_3 \ldots p_m, $$ the product of the first $m$ prime numbers.