4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Your link's broken. $\endgroup$ – shade4159 Nov 6 '13 at 20:41
  • $\begingroup$ 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$ $\endgroup$ – Tim Ratigan Nov 6 '13 at 20:55
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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