Prove that $\tau(2^n-1) \geq \tau(n)$ for all positive integers $n$.

Question

Prove that $\tau(2^n-1) \geq \tau(n)$ for all positive integers $n$.

Note that $\tau(2^n-1)=\sum_{d|2^n-1}{1}$. I try to prove by induction.

Base case: When $n=1$, we have $\tau(2-1)=\tau(1)$. Hence, the inequality is true.

Fix an $n$. Assume that the inequality $\tau(2^n-1) \geq \tau(n)$, which is $\sum_{d|2^n-1}{1} \geq \sum_{d|n}{1}$ is true for $n$. Note that $\sum_{d|2^{n+1}-1}{1}=\sum_{d|2^{n}-1}{1}+1 \geq \sum_{d|n}{1}+1=\sum_{d|n+1}{1}$

I don know whether the equality above hold or not. Can anyone guide me?

Answer 1

Hint: If $d\mid n$ then we have $2^{d}-1\mid 2^{n}-1$.