10
$\begingroup$

Just an observation:

$$x!-(x-1)!-(x-2)!-...-1!=y$$

It is observed that $y$ is always divisible by $3$. Why is this so?

$\endgroup$
  • 11
    $\begingroup$ $2!-1!$ is not divisible by $3$. $\endgroup$ – Henricus V. Dec 26 '16 at 6:16
19
$\begingroup$

This does not hold for $x < 3$. Otherwise, observe that $$ x! - \sum_{j=1}^{x-1} (x-j)! = x! - \sum_{j=1}^{x-3} (x-j)! - (2! + 1!) $$ the former is divisible by $3$ since $x_j \geq 3$ for all such $j$. The latter is divisible by $3$ with simple arithmetic. Hence the entire expression is divisible by $3$, when $x \geq 3$.

$\endgroup$
  • 3
    $\begingroup$ Similarly, for $x \ge 5$ we will have $y \equiv 2 \pmod 5$ because $-(4!+3!+2!+1!)\equiv 2 \pmod 5$ $\endgroup$ – Ross Millikan Dec 26 '16 at 6:22
18
$\begingroup$

A bit of an interesting pattern that has an easy explanation. Note, that this is only true where $n > 2$, since $2! - 1! = 2 - 1 = 1$ which is evidently not divisible by 3.

This is due to a simple consequence from the fact that for every $n >2$, $n!$ is divisible by $3$. Why? $$n! = n \cdot n - 1 \cdot n-2 \ \cdot \ ....... \ \cdot 3 \cdot 2 \cdot 1$$ And $3$ is a factor...so obviously $3$ divides $n!$. Without going into modular arithmetic as it may not be an area you are familiar with, if $x, y$ are divisible by $3$, then so is $x - y$ (You can try verifying this by yourself if you don't think this is convincing).

So the only possible violations in $n! - (n-1)! - (n-2)! - .... - 1!$ being divisible by $3$ is from $-2! - 1!$ since $$\underbrace{n! - (n-1)! - (n-2)! - (n-3)! - (n-4)! - (n-5)! - ..... }_\text{All divisible by 3} - 2! - 1!$$ Noting that $2 + 1 = 3$ (subtracting by 3 at the end), then the result follows immediately.

(I just want to say that it is these exact same patterns that to me seemed extraordinary at the time, that made me get interested in mathematics).

$\endgroup$
  • $\begingroup$ Because at the end, $-2! - 1!$ is the same thing as $-(2+1)$ or subtracting by 3 equivalently $\endgroup$ – q.Then Dec 26 '16 at 7:18
  • $\begingroup$ This answer was clearer than Henry's answer IMO. Nice job $\ddot\smile$ $\endgroup$ – Simply Beautiful Art Dec 26 '16 at 17:04
  • $\begingroup$ @SimpleArt, thanks! It feels nice to have an 14K rep person say that $\endgroup$ – q.Then Dec 26 '16 at 17:05
  • $\begingroup$ D: 14K? I think I'm closer to 15K IMO $\endgroup$ – Simply Beautiful Art Dec 26 '16 at 17:06
  • $\begingroup$ Actually, I wanna get to 15K today, but I'm not sure how much more rep I could get. $\endgroup$ – Simply Beautiful Art Dec 26 '16 at 17:08
5
$\begingroup$

This works only for $x \ge 3$ (as $2! - 1!$ is not divisible by $3$). The reason this works is simple. First, think about the case $x = 3$, so that you have $y = 3! - 2! - 1!$.

$3!$ is clearly divisible by $3$, and $-2! - 1! = -3$, so this is also divisible by $3$. Therefore, $y$ is divisible by $3$.

For all $x > 3$, you have these same terms from $x = 3$, with all larger factorial up to $x$ being added/subtracted off. I've already shown that it works for $x=3$, so neglect those terms momentarily. Every factorial higher than $3$ must, by definition, have $3$ as a factor, as it can be written as $1*2*3*....*x$.

We can therefore conclude that $y$ must be divisible by $3$ for all $x \ge 3$.

$\endgroup$
2
$\begingroup$

As already pointed out, this only works for $x\ge3$. The reason can be seen if we rewrite your expression as

$$-1!-2!-3!-\cdots-(x-1)!+x!$$

and observe that $-1!-2!=-3$, and all the terms that are added or subtracted after that, from $3!$ thru $x!$, are divisible by $3$.

$\endgroup$
2
$\begingroup$

$$ \begin{align} 3+\overbrace{\sum_{k=3}^{n-1}(k-1)k!}^{\substack{\text{divisible by $3$}\\\text{for $n\ge3$}}} &=1+\sum_{k=1}^{n-1}(k-1)k!\\ &=1+\sum_{k=1}^{n-1}[(k+1)!-2k!]\\ &=1+\sum_{k=2}^nk!-2\sum_{k=1}^{n-1}k!\\ &=n!-1-\sum_{k=2}^{n-1}k!\\ &=n!-\sum_{k=1}^{n-1}k!\\ \end{align} $$

$\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.