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$
11
  • 1
    $\begingroup$ Three real? It is obvious but they are integers it is more interesting $\endgroup$
    – IrbidMath
    Feb 19, 2019 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$ Feb 19, 2019 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, 2019 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$
    – qualcuno
    Feb 19, 2019 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, 2019 at 6:06

2 Answers 2

13
$\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$
4
  • $\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$ Feb 19, 2019 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, 2019 at 7:46
  • 1
    $\begingroup$ I have made a quick edit, my proof was assuming $p$ prime, but it is easy to fix that. $\endgroup$
    – user568543
    Feb 19, 2019 at 8:15
  • $\begingroup$ My reference to prime powers was a mistake on my part too. $\endgroup$
    – J.G.
    Feb 19, 2019 at 9:29
4
$\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$
3
  • $\begingroup$ @Oldboy It's such an honor for me for your alternative effort. Outstanding for better learning process. $\endgroup$ Feb 19, 2019 at 8:18
  • 1
    $\begingroup$ @AnirbanNiloy You are welcome. Keep up the good work! $\endgroup$
    – Saša
    Feb 19, 2019 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$
    – Saša
    Feb 19, 2019 at 10:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .