PlanetMath: unambiguity of factorial base representation

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

unambiguity of factorial base representation

(Definition)

Theorem 1 For all positive integers , it is the case that

$\displaystyle n! = 1 + \sum_{k = 1}^{n - 1} k \cdot k!$

Proof. We first consider two degenerate cases. When

, the sum has no terms because the lower limit is bigger than the upper limit. By the convention that a sum with no terms equals zero, the equation reduces to

, which is correct.

Next, assume that . Note that

$\displaystyle k \cdot k! = (k + 1) k! - k! = (k + 1)! - k!,$

hence, we have a telescoping sum:

$\displaystyle \sum_{k = 1}^{n - 1} k \cdot k! = \sum_{k = 1}^{n - 1} \left( (k + 1)! - k! \right) = n! - 1$

Adding 1, we conclude that

$\displaystyle n! = 1 + \sum_{k = 1}^{n - 1} k \cdot k!$

$\qedsymbol$

Theorem 2 If $d_m \ldots d_2 d_1$ is the factoradic representation of a positive integer , then $(d_m + 1) \, m! > n \ge d_m \cdot m!$

Proof. By definition,

$\displaystyle n = d_m \cdot m! + \sum_{k=1}^{m-1} d_k \cdot k! .$

Since each term of the sum is nonnegative, the sum is positive, hence $n \ge d_m \cdot m!$ . Using the fact that $0 \le d_k < k$ to bound each term in the sum, we have

$\displaystyle n \le d_m \cdot m! + \sum_{k=1}^{m-1} k \cdot k!.$

By theorem 1, the right-hand side equals

, so we have $n \le d_m \cdot m! + m! - 1$ , which is the same as saying $(d_m + 1) \, m! > n$ . $\qedsymbol$

Theorem 3 If $d_m \ldots d_2 d_1$ and ${d'}_{m'} \ldots {d'}_2 {d'}_1$ are distinct factoradic representations with $d_m \neq 0$ and ${d'}_{m'} \neq 0$ (i.e. not padded with leading zeros), then they denote distinct integers.

Proof. Let $n = \sum_{k=1}^m d_k \cdot k!$ and let $n' = \sum_{k=1}^{m'} {d'}_k \cdot k!$ .

Suppose that and are distinct. Without loss of generality, we may assume that . Then, $(m+1)! \le {m'}!$ . By theorem 2, we have $n < (d_m + 1) \, m!$ and $d_{m'} \cdot {m'}! \le n'$ . Because $d_m \le m$ , we have $(d_m + 1) \,m! \le (m + 1) \, m! = (m + 1)!$ . Because $d_{m'} \neq 0$ , we have . Hence, , so does not equal .

To complete the proof, we use the method of infinite descent. Assume that factoradic representations are not unique. Then there must exist a least integer such that has two distinct factoradic representations $d_m \ldots d_2 d_1$ and ${d'}_{m'} \ldots {d'}_2 {d'}_1$ with $d_m \neq 0$ and ${d'}_{m'} \neq 0$ . By the conclusion of the previous paragraph, we must have . By theorem 2, we must have $d_m = {d'}_m$ . Let be the chosen such that $d_{m_1} \neq 0$ but $d_{m_1 + 1} = \cdots = d_{m-1} = 0$ and let be the chosen such that ${d'}_{m_2} \neq 0$ but ${d'}_{m_2 + 1} = \cdots = {d'}_{m-1} = 0$ . Then $d_{m_1} \ldots d_2 d_1$ and ${d'}_{m_2} \ldots {d'}_2 {d'}_1$ would be distinct factoradic representations of $n - d_m \cdot m!$ whose leading digits are not zero but this would contradict the assumption that is the smallest number with this property. $\qedsymbol$