# Positive integers $n$ such that $\sum_{k=1}^{n} k!$ divides $(n + 1)!$

I need help writing a proof by induction for this problem.

Recall that $n! = 1 \times 2 \times 3 \times \ldots \times n$. Find all positive integers $n$ such that $1! + 2! + \ldots + n!$ divides $(n + 1)!$.

Here I have what I have already tried:

http://openstudy.com/study#/updates/527aa321e4b0dc82d54350ff

Here I have what I have already tried.

• Your link's broken. – shade4159 Nov 6 '13 at 20:41
• In order for $S=\sum_{k=1}^n k!|(n+1)!$, all prime divisors of $S$ must be $\leq n+1$. This requires that $S\not\equiv0 \pmod{p}$ for all prime $p> n+1$. The question is when you can find such $p$ – Tim Ratigan Nov 6 '13 at 20:55

## 2 Answers

Assume $S_n=\sum_{k=1}^n k!$ divides $(n+1)!$. Then $\exists \ell\in\mathbb{N}$ such that $\ell S_n=(n+1)!$. Then $\ell S_{n-1}+\ell n!=(n+1)!$, $\ell S_{n-1}=(n+1-\ell)(n)!$. Note that as $n$ increases, $n+1-\ell$ approaches $1$, and plugging in numbers will tell you $n+1-\ell$ never exceeds $1\frac{4}{11}$ as:

\begin{align} \left(n-\frac{n!}{S_{n-1}}\right)-\left(n+1-\frac{(n+1)!}{S_n}\right)=\frac{-S_n\cdot n!+S_{n-1}\cdot (n+1)!}{S_nS_{n-1}}-1&>0 \\ S_{n-1}(n+1)!-S_n\cdot n!&>S_nS_{n-1} \\ S_{n-1}(n+1)!&>S_n(S_{n-1}+n!) \\ (n+1)!S_{n-1}>S_n^2 \end{align}

So for sufficiently large $n$ (which can be checked to be $4$), it is clear the inequality holds and $n+1-\ell$ is decreasing

This means that, if $S_n|(n+1)!$, $S_{n-1}|(n+1-\ell)n!=n!$. Inductively, $S_k|(k+1)!$ for all $1\leq k\leq n$. Since $S_3\not|4!$, $S_n\not|(n+1)!$ for all $n\geq 3$.

This makes the solutions $n=1,2$

I'll give credit where credit is due: I borrowed the initial idea from amistre64 in the forum you linked to.

First, we know that $1!+2!+3!+....+n!$ is odd. Since half the numbers before $(n+1)!$ are even, we have that the highest power of two that divides $(n+1)!$ is $\ge 2^{\lfloor \frac{n+1}{2} \rfloor}$ .

Therefore, if we have $(1!+2!+3!+....+n!)k=(n+1)!$, for some $k$, then since the RHS is multiple of $2^{\lfloor \frac{n+1}{2} \rfloor}$, $k$ must also be one, and we have: $$k(1!+2!+3!+....+n!)\ge 2^{\lfloor \frac{n+1}{2} \rfloor}n!$$

It is then easy to argue by induction that $2^{\lfloor \frac{n+1}{2} \rfloor}> n+1$ for $n\ge5$. And solutions are $n=1,2$