Category Archives: proof

Möbius inversion

In my last post we saw that , that is, the Möbius function is the inverse of with respect to Dirichlet convolution. This directly leads to an interesting principle called Möbius inversion. Möbius inversion. Suppose is defined for as the … Continue reading

Posted in combinatorics, proof | Tagged , , , , | 3 Comments

Dirichlet convolution and the Möbius function

Recall from last time that the Dirichlet convolution of two functions and is written and defined by: where the sum is taken over all possible factorizations of into a product of positive integers. Last time we saw that is commutative … Continue reading

Posted in combinatorics, proof | Tagged , , , | 1 Comment

Dirichlet convolution

Let and be two functions defined on the positive integers. Then the Dirichlet convolution of and , written , is another function on the positive integers, defined as follows: The sum is taken over all possible factorizations of into a … Continue reading

Posted in combinatorics, proof | Tagged , , , | 7 Comments

The Möbius function proof, part 2 (the subset parity lemma)

Continuing from my previous post, we are in the middle of proving that satisfies the same equation as , that is, and that therefore for all , that is, is the sum of all the th primitive roots of unity. … Continue reading

Posted in arithmetic, combinatorics, complex numbers, primes, proof | Tagged , , , , , , , , , | 2 Comments

Totient sums

I took a bit of a break to travel to Japan for a conference, but I’m back now to continue the series I started with Post Without Words #10, a follow-up post, and Post Without Words #11. Recall that we … Continue reading

Posted in geometry, pattern, pictures, posts without words, proof | Tagged , , , , , | 4 Comments

Post without words #11

Posted in geometry, pattern, pictures, posts without words, proof | Tagged , , , , , | 7 Comments

The route puzzle

While poking around some old files I came across this puzzle: (Click for a larger version.) I didn’t make it, and I have no idea where I got it from (do you know?). But in any case, wherever it comes … Continue reading

Posted in arithmetic, challenges, number theory, proof, puzzles | Tagged , , , , , , | 7 Comments