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!$).

Printable View

- Jan 29th 2008, 02:59 AMjames_bondFactors 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!$). - Jan 29th 2008, 03:37 AMmr fantastic
- Jan 29th 2008, 03:40 AMjames_bond
- Jan 29th 2008, 07:07 PMThePerfectHacker
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$.

- Jan 30th 2008, 04:28 AMOpalg
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. - Jan 30th 2008, 07:12 AMThePerfectHacker
- Jun 4th 2008, 01:58 PMduggaboya little confused
Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let http://www.mathhelpforum.com/math-he...d1058765-1.gif. Divide x by n+1, getting a quotient q and a remainder r, so that http://www.mathhelpforum.com/math-he...f396952f-1.gif, where http://www.mathhelpforum.com/math-he...82df4850-1.gif and http://www.mathhelpforum.com/math-he...7dd9157d-1.gif. (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, http://www.mathhelpforum.com/math-he...c5461872-1.gif, where the numbers c_j are distinct divisors of n!. Then http://www.mathhelpforum.com/math-he...0e70e550-1.gif. Define http://www.mathhelpforum.com/math-he...2b8e8394-1.gif and http://www.mathhelpforum.com/math-he...fa653b07-1.gif. These numbers are all distinct (because http://www.mathhelpforum.com/math-he...fce1bbaa-1.gif 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?? - Jun 5th 2008, 01:14 AMOpalg