1. ## Factors of n!

Prove that $\displaystyle \forall x\le n!$
$\displaystyle x=\sum_{i=1}^kd_i$ where $\displaystyle k\le n$ (and $\displaystyle d_i$ are different factors of the number $\displaystyle n!$).

2. Originally Posted by james_bond
Prove that $\displaystyle \forall x\le n!$
$\displaystyle x=\sum_{i=1}^kd_i$ where $\displaystyle k\le n$ (and $\displaystyle d_i$ are different factors of the number $\displaystyle n!$).
So you basically need to show that the sum of the divisors of n! is always less than or equal to n!

3. Originally Posted by mr fantastic
So you basically need to show that the sum of the divisors of n! is always less than or equal to n!

Not exactly, I need to show that every number not greater than $\displaystyle n!$ can be expressed as a sum of at most $\displaystyle n$ different factors of $\displaystyle n!$.

4. This is a proof outline. The proof is on induction on the factorial. It is clearly true for small numbers. We will prove it is true for $\displaystyle (n+1)!$. Let $\displaystyle x < (n+1)!$. If $\displaystyle x\leq n!$ then by induction there exists distinct $\displaystyle d_i$ so that $\displaystyle x=d_1+...+d_k$. Thus, it is safe to assume that $\displaystyle n!+1\leq x \leq (n+1)! - 1$. The goal is to find a factor(s) $\displaystyle n!\leq d<x$ of $\displaystyle (n+1)!$ such that $\displaystyle x - d \leq n!$ then by induction $\displaystyle x - d = d_1+...+d_k$ where $\displaystyle d_i$ are distinct and $\displaystyle d_i | n!$ thus clearly $\displaystyle d_i| (n+1)!$ and $\displaystyle d > d_i$ thus it is distinct too. Which means $\displaystyle x = d+d_1+...+d_k$.

5. Originally Posted by james_bond
Prove that $\displaystyle \forall x\le n!$
$\displaystyle x=\sum_{i=1}^kd_i$ where $\displaystyle k\le n$ (and $\displaystyle d_i$ are different factors of the number $\displaystyle n!$).
Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let $\displaystyle 1\leqslant x\leqslant (n+1)!$. Divide x by n+1, getting a quotient q and a remainder r, so that $\displaystyle x = q(n+1)+r$, where $\displaystyle 0\leqslant q < n!$ and $\displaystyle 1\leqslant r \leqslant n+1$. (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis, $\displaystyle q = c_1+c_2+\ldots+c_n$, where the numbers c_j are distinct divisors of n!. Then $\displaystyle x = q(n+1)+r = (c_1+c_2+\ldots+c_n)(n+1) + r$. Define $\displaystyle a_j = c_j(n+1)\;\;(1\leqslant j\leqslant n)$ and $\displaystyle a_{n+1} = r$. These numbers are all distinct (because $\displaystyle r\leqslant n+1$ and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved.

6. Originally Posted by Opalg
(Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)
If the part r=0 is the thing that bothers you then if you do that way then it still works because if r=0 then you just are not adding anything to the number and the proof still works.

7. ## a little confused

Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let . Divide x by n+1, getting a quotient q and a remainder r, so that , where and . (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis,
, where the numbers c_j are distinct divisors of n!. Then . Define and . These numbers are all distinct (because and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved.

Does this induction prove that the results are composite numbers??

8. Originally Posted by duggaboy
Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let . Divide x by n+1, getting a quotient q and a remainder r, so that , where and . (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis,
, where the numbers c_j are distinct divisors of n!. Then . Define and . These numbers are all distinct (because and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved.

Does this induction prove that the results are composite numbers??
No. It's clearly true that most of the numbers $\displaystyle c_j(n+1)$ must be composite. But it's possible that $\displaystyle c_j$ could be 1, and n+1 prime. Also, the "remainder" term r might well be prime.