Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $ \Lambda(k) $ denote the von Mangoldt function: $$ \Lambda(k) \stackrel{\text{def}}{=} \begin{cases} 0 & \text{if $ k $ is not a prime power}, \\ \ln(p) & \text{if $ k = p^{j} $}. \end{cases} $$ Also, let $ \lfloor x \rfloor $ be the floor function. Can anyone prove the following identity $$\sum_{k=1}^n \ln(k)= \sum_{k=1}^n \Lambda(k) \left\lfloor \frac{n}{k} \right\rfloor$$

share|improve this question
It might help if you supplied a bit of background. Where does this come from and why do you expect it to be true? –  Tobias Kildetoft Dec 30 '12 at 4:22
@Ethan This question is actually suitable for induction (apart from that, it's not nice to laugh at people's attempts). Those identities and their generalizations are proved by the simple identity $\ln m = \sum_{d|m} \Lambda(d)$ (which is often the definition of $\Lambda$) and interchanging the order of summation. The curios floor functions count multiples of some $x$ less than some $y$ that lie in a certain arithmetic progression. –  Ofir Dec 30 '12 at 10:51
@Ethan "being proved by simple methods like induction" Induction is by no means a trivial method. One of the most important objects in mathematics, namely, the set of natural numbers, is defined inductively. Any statement which needs to be proved for all $n$ needs to rely on induction at some point. –  user17762 Dec 30 '12 at 22:34
@Ethan It is not polite to change the question so much after someone went to a fair bit of trouble to answer. –  Erick Wong Dec 31 '12 at 2:24
@Ethan - I agree with Erick. You changed the question after I answered, without giving an explanation. So my answer has been accepted without being a suitable answer for the current question. If you had a new question, you should have opened a new question or asked me in a comment to my answer. What would have happened if someone gave an answer to your new question? You would've accepted his answer instead of mine, as required. Anyway, I answered your new question because the same method applies. –  Ofir Dec 31 '12 at 8:36

2 Answers 2

up vote 2 down vote accepted

EDIT: I'll prove the single identity you now wrote, for completeness sake. As in my original answer, note that $\Lambda * 1 = \log n$, where $*$ denotes convolution.

In general, if $f,g$ are functions from $\mathbb{N}$ to $\mathbb{C}$ and $F(x)=\sum_{n\le x}f(x), G(x) = \sum_{n\le x} g(x)$ are the corresponding summatory functions, we have the following identity: $$\sum_{1\le n \le x} (f*g)(n) = \sum_{1\le n \le x} \sum_{d|n} f(d)g(n/d) = \sum_{1 \le d \le x} f(d) (\sum_{d|n, 1\le n \le x}g(n/d))=$$ The number of multiples of d between $1$ and $x$ is $\lfloor \frac{x}{d} \rfloor$, thus: $$\sum_{1 \le d \le x} f(d) (\sum_{1 \le i \le \lfloor \frac{x}{d} \rfloor} g(i))=\sum_{1 \le i \le x}f(i)G(\frac{x}{i})$$ Similarly, $$\sum_{1\le n \le x} (f*g)(x) =\sum_{1 \le i \le x}g(i)F(\frac{x}{i})$$

If you've heard about "Dirichlet's Hyberbola Method", it is just a refinement of this which states: $$\sum_{1\le n \le x} (f*g)(n) =\sum_{1 \le i \le V}f(i)G(\frac{x}{i}) + \sum_{1 \le j \le U}g(j)F(\frac{x}{j}) - F(V)G(U)$$ Where U,V are positive reals such that $UV=x$. The proof is similar and has a geometric interpretation - hence the name. If you take $U=x,V=1$ or $U=1,V=x$, you get the original identities easily.

Back to your specific identity - just plug $f=\Lambda, g=1$ (i.e. $g$ is identically 1), and you'll find: $$\sum_{1\le n \le x} (\Lambda*1)(x) =\sum_{1 \le i \le x}f(i)G(\frac{x}{i})$$ $$=\sum_{1 \le i \le x} f(i)\lfloor \frac{x}{i} \rfloor =\sum_{1 \le i \le x}\lfloor \frac{x}{i} \rfloor \Lambda(x)$$

Remark: if you choose $f=\mu, g=1$, you find $1=\sum_{1 \le i \le x} \lfloor \frac{x}{i} \rfloor \mu(x)$ for $x\ge 1$, since $\mu * 1 = \delta_{n,1}$. This is another famous identity. Challenge - use this to prove $|\sum_{n=1}^{x} \frac{\mu(n)}{n}| \le 1$.

(Answer to original question - might contain some calculation mistake)

I'll elaborate on my partial answer from the comments. First, we need to agree that $\ln m = \sum_{d|m} \Lambda(d)$. The simplest way to prove it is to use the formula for $\Lambda$ and just plug it in. This identity is very basic, and is fruitful in analytic number theory - it allows one to compute certain interesting sums, such as $\sum_{m \le n} \sum_{d|m} \Lambda(d) = \ln n! \sim n \ln n$. Another way to prove it is to use Möbius Inversion.

Anyway, consider the first sum: $$\sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \ln(3k+1) = \sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \Lambda(3k + 1) \left\lfloor \frac{n}{9k + 3} + \frac{2}{3} \right\rfloor + \sum_{k=0}^{\left\lfloor (n - 2)/3 \right\rfloor} \Lambda(3k + 2) \left\lfloor \frac{n}{9k + 6} + \frac{1}{3} \right\rfloor$$

We'll use the identity I mentioned: $$\sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \ln(3k+1)= \sum_{k=0}^{\left\lfloor (n - 1)/3 \right\rfloor} \sum_{d | 3k+1} \Lambda(d)=$$ $$\sum_{d \le 3 \left\lfloor (n - 1)/3 \right\rfloor + 1} \Lambda(d) \sum_{k=0, d|3k+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1$$

Note that if $3|d$ then it appears with weight equal to zero, since $3k+1$ is never divisible by $3$. Thus we can divide the $d$'s into 2 types - $3k+1$ and $3k+2$:

$$\sum_{3k+1 \le 3\left\lfloor (n - 1)/3 \right\rfloor +1} \Lambda(3k+1) (\sum_{i=0, 3k+1|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1 )+ \sum_{3k +2 \le 3\left\lfloor (n - 1)/3 \right\rfloor + 1} \Lambda(3k+2) (\sum_{i=0, 3k+2|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1)=$$ $$\sum_{k \le \left\lfloor (n - 1)/3 \right\rfloor} \Lambda(3k+1) (\sum_{i=0, 3k+1|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1 )+ \sum_{k \le \left\lfloor (n - 1)/3 \right\rfloor - 1} \Lambda(3k+2) (\sum_{i=0, 3k+2|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1)$$ (Note that I changed the names of some of the variables)

The next logical step is to prove $\sum_{i=0, 3k+1|3i+1}^{\left\lfloor (n - 1)/3 \right\rfloor} 1 = \left\lfloor \frac{n}{9k + 3} + \frac{2}{3} \right\rfloor$. There's no fun in it, but I'll do it :) Note that if $3k+1 | 3i+1$ then $3i+1 = (3k+1)(3r+1)$ for some $r$. We're actually counting those $r$'s. $r$ is non-negative and $(3k+1)(3r+1) \le 3\left\lfloor (n - 1)/3 \right\rfloor+1$, i.e. $0 \le r \le \frac{1}{3} (\frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{3k+1} - 1)$. Thus it remains to show: $$1 + \left\lfloor \frac{1}{3} (\frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{3k+1} - 1) \right\rfloor= \left\lfloor \frac{n}{9k + 3} + \frac{2}{3} \right\rfloor$$ The LHS simplifies a little - $$\left\lfloor \frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{9k+3} - \frac{1}{3} + 1 \right\rfloor = \left\lfloor \frac{3 \left\lfloor (n - 1)/3 \right\rfloor + 1}{9k+3} + \frac{2}{3} \right\rfloor = \left\lfloor \frac{n}{9k+3} + \frac{2}{3} - \frac{\{\frac{n-1}{3} \}}{3k+1} \right\rfloor$$ And indeed $\left\lfloor \frac{n}{9k+3} + \frac{2}{3} - \frac{\{\frac{n-1}{3} \}}{3k+1} \right\rfloor = \left\lfloor \frac{n}{9k+3} + \frac{2}{3} \right\rfloor$! For $n \equiv 1 \mod 3$, this is immediate. In the other cases, this is also true, since otherwise $ \frac{n}{9k+3} $ is really close to $\frac{1}{3}$ from above (in the sense that it's $\frac{3\text{ or }6}{9k+3}=\frac{3\{\frac{n-1}{3} \}}{9k+3}$ away), which can't happen since $k \le \left\lfloor (n - 1)/3 \right\rfloor$.

I am a bit lying - if $k \le \frac{n-7}{3}$, then $ \frac{n}{9k+3}-\frac{1}{3} \ge \frac{3k+7 - 3k-1}{9k+3}=\frac{6}{9k+3} \ge \frac{3\{\frac{n-1}{3}\}}{9k+3}$, as we wanted. But I am not sure about $\frac{n-6}{3} \le k \le \lfloor \frac{n-1}{3} \rfloor$, maybe I did some calculation mistake.

The other half of the sum is similar, and so are the rest of the identities - simply use the relation between $\ln n$ and $\Lambda(d)$, and count numbers $i$ that satisfy: $0\le i \le t, d|ai+b$.

share|improve this answer

A perhaps simpler proof, using the $p$-adic expansion of $n!$:

$$\log(n!)=\sum_{p \text{ prime}}\log(p)\left(\left \lfloor \frac{n}{p} \right \rfloor+\left \lfloor \frac{n}{p^2} \right \rfloor+...\right)=\sum_{k=1}^n \Lambda(k)\left \lfloor \frac{n}{k} \right \rfloor. $$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.