2
$\begingroup$

I decided to prove this by induction and I'm not sure if this is a valid proof, or maybe there is something that I'm missing. Anyway, I'd appreciate some feedback nonetheless.

Note: This proof assumes knowledge of the Möbius function.

Proof that $\sum_{k=1}^{n}\mu(k!)=1$ for $n \geq 3$:

Base Case

  • Let $n=3$ and test:

$\sum_{k=1}^{3}\mu(k!) = \mu(1) + \mu(2 \cdot 1) + \mu(3 \cdot 2 \cdot 1)$

$=(1)+(-1)+(1)=1$

  • True for base case ($n=3$).

Induction Hypothesis

  • Assume that it is true for $m$ for $m \geq 3$:

$\sum_{k=1}^{m}\mu(k!)=1$

Inductive Step:

  • Using the Inductive Hypothesis as a premise, we have:

$\sum_{k=1}^{m+1}\mu(k!)=(\sum_{k=1}^{m}\mu(k!)=1)+\mu((m+1)!)$

$=1+\mu((m+1)!)$

Since $m\geq 3$, we have $m+1\geq 4$. But then $(m+1)!=(m+1)(m)...(4)(3)(2)(1)$ Notice the factor of $(4)$ in the expanded sum.

Since $4=2^2$ is a square number, $(m+1)!$ has a squared factor, and according to the definition of the Möbius function, $\mu((m+1)!)=0$.

Finally, we have

$=1+\mu((m+1)!) = 1+0 = 1$

  • True for inductive step, therefore true for all cases.
$\endgroup$
3
  • 6
    $\begingroup$ I am thinking a much easier argument. Note that $$0= \mu(4!) = \mu(5!) = \mu(6!) = \mu(7!) = \mu(8!) = ...$$ so your sum is simply $$\mu (1!) + \mu(2!) + \mu(3!) + 0+ \dots +0= 1-1+1 + 0+ \dots +0=1$$ OK, this is basically the same argument of yours, but much shorter. $\endgroup$
    – Crostul
    Aug 25, 2016 at 12:19
  • 1
    $\begingroup$ Dangit! How did I not think to simply do that? Thanks! I'll just use this. :) $\endgroup$
    – Tristan Batchler
    Aug 25, 2016 at 12:23
  • 2
    $\begingroup$ Actually the dots "$\dots$" hide induction. A formal and precise proof would be yours, but dots are universally accepted and understood in math. $\endgroup$
    – Crostul
    Aug 25, 2016 at 12:25

0

Reset to default

You must log in to answer this question.