Prove that
d(n) are the positive factors of n. Ex: d(12) = 6 (the factors are 1, 2, 3, 4, 6, 12).
Well, it took a while but I think I got it. Of course, using Dirichlet's product I suppose it could be way faster, but I'm assuming you haven't yet covered that, so let's try it the long way
Let be the prime decomposition of n, with . We'll need the following easy lemma:
Lemma: The number of positive divisors of n is
Now,by induction on n = the number of distinct prime divisors of n: if , then , and we're cool.
Assume now the claim's true for all natural numbers divisible by up to n-1 different primes, and let and define
, then:
, the 2nd equality being due to the inductive hypothesis and the fact that the factor appears
multiplying each and every one of the divisors of m , . Thus:
, since . Q.E.D.
Tonio