6
$\begingroup$

Let $n$, $p$ and $r$ be three positive integers. Prove that for $n \geqslant 3, r>1$, $$\sum_{k = 0}^{n} k! \neq p^\text{r}$$

SOURCE: BANGLADESH MATH OLYMPIAD (Preaparatory Question)

I am not so familiar with such a this kind of problem. Seeing that problem, I became little bit curious about what the text states and what will be its conception?

I couldn't solve the problem. Moreover, I don't know about the formula of $\sum k!$. Is there any? And I couldn't realize the essence of $p^\text{r}$ and what the reason is behind the fact the summation can't be equal to $p^r$ for some integer $p$.

Any kind of reference or conception will massively help me start with some approach to solve the above problem. Thanks for your support and effort in advance.

$\endgroup$
  • 1
    $\begingroup$ Three real? It is obvious but they are integers it is more interesting $\endgroup$ – Ameryr Feb 19 at 5:25
  • $\begingroup$ @Ameryr I am very novice and little experienced at this case. You can suggest me a edit and I will be highly glad to approve it. $\endgroup$ – Anirban Niloy Feb 19 at 5:26
  • 1
    $\begingroup$ Considering $n$ is one of the limits of $\sum$ here, that one at least must be an integer $\endgroup$ – programmer Feb 19 at 5:29
  • 1
    $\begingroup$ Aren't there any other additional restrictions? Otherwise the result is true for some choices of $p$ and $r$. Specifically, one could choose $r = 1$ and $p = \sum_{k = 0}^n k!$... $\endgroup$ – Guido A. Feb 19 at 5:37
  • 2
    $\begingroup$ Well, here's a related question on the formula for sums of factorials. $$\sum_{k=0}^n k! = \frac{1}{e}\left( \mathrm{Ei}(1) + i\pi + (-1)^{n+1}\Gamma(n+2)\Gamma(-n-1,-1) \right) $$ where $\mathrm{Ei}(x)$ is the exponential integral and $\Gamma(x,a)$ is the upper incomplete gamma function. $\endgroup$ – Infiaria Feb 19 at 6:06
11
$\begingroup$

The question asks about the prime factorisation of $\sum_{k=0}^{n}k!$. The first thing to notice is that you have $0!=1!=1$ and all the other terms are divisible by 2, so the sum is divisible by 2. Thus if we are looking for a counterexample, we must have $p$ even, and so since $r>1$, $4$ divides the sum.

Now, the sum begins $0!+1!+2!+3!=10$, and then all terms after this are $k!$ for $k\ge4$. Thus, for $n\ge3$, $4$ does not divide the sum, a contradiction.

$\endgroup$
  • $\begingroup$ What is counterexample? I haven't read yet anything about it. Would you please clearify the point that for $n \geqslant 3$, 4 doesn't divide the sum? Besides, the power of 2 would have to be 2 or 1. Except this, the solution was very helpful. $\endgroup$ – Anirban Niloy Feb 19 at 7:35
  • 2
    $\begingroup$ @AnirbanNiloy A counterexample is an instance of a claimed general rule failing, making it false. So if it's claimed $\sum_{k=0}^n n!$ is never a prime power, a counterexample would be a choice of $n$ for which it is. As Cambridge grad shows, such a counterexample would be a power of $2$. The point about divisibility by $4$ is that later factorials are divisible by $4!$ and hence $4$, and so later sums are, like $10$, $2$ more than a multiple of $4$. $\endgroup$ – J.G. Feb 19 at 7:46
  • $\begingroup$ I have made a quick edit, my proof was assuming $p$ prime, but it is easy to fix that. $\endgroup$ – George R Feb 19 at 8:15
  • $\begingroup$ My reference to prime powers was a mistake on my part too. $\endgroup$ – J.G. Feb 19 at 9:29
3
$\begingroup$

Just for fun, I will solve the same problem but with $0!$ removed:

Solve: $$1!+2!+\dots+n!=p^r$$ ...for $n,p,r\in N, r\ge2, n\ge3$

Denote the sum of the first $n$ factorials with $a_n$:

$$a_n=\sum_{k=1}^n k!$$

It is obvious that for $n\ge3$:

$$3\mid a_n$$

Why is that so? 3 divides 1!+2! and 3 divides all factorials starting from 3! So the sum of factorials $a_n$ must be divisible by 3 for $n>3$. It means that the $p^r$ must be divisible by 3 which is possible only if:

$$3\mid p\iff p=3q$$

In other words:

$$a_n=\sum_{k=1}^n k!=3^rq^r\tag{1}$$

Suppose that $r>=3$. It means that the right hand side is divisible by 27 and therefore it means that $a_n$ has to be divisible by 27 as well. Notice that 27 divides all factorials starting from $9!$. So if $a_8$ is divisible by 27, so it is $a_9, a_{10},\dots$.

You can check manually that $$a_8=1!+2!+3!+4!+5!+6!+7!+8!=46233$$

Therefore:

$$27\nmid a_8$$

Consequentially, for all $n\ge9$:

$$27\nmid a_n$$

So we have a contradiction for all big enough values of $n$. We just have to check a few starting values manually. Indeed, if you check all values from $a_1$ to $a_8$ you will see that only $a_7=5913$ is divisible by 27. But number $5913=3^4\times73$ is not of the form $p^r$.

So there is no solution for any $r\ge3$.

We have yet to consider a case for $r=2$:

$$a_n=p^2$$

It can be easily shown (see proof here) that:

$$1!+2!+3!=3^2$$

...is the only solution of the problem.

$\endgroup$
  • $\begingroup$ @Oldboy It's such an honor for me for your alternative effort. Outstanding for better learning process. $\endgroup$ – Anirban Niloy Feb 19 at 8:18
  • 1
    $\begingroup$ @AnirbanNiloy You are welcome. Keep up the good work! $\endgroup$ – Oldboy Feb 19 at 8:38
  • 1
    $\begingroup$ @PeterTaylor Initially, I took $p$ to be a prime number but forgot to mention that. I have corrected my solution to allow for any possible value of $p$. This just made the problem more interesting, thanks for reporting the mistake. $\endgroup$ – Oldboy Feb 19 at 10:05

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.