# unambiguity of factorial base representation

###### Theorem 1.

For all positive integers $n$, it is the case that

 $n!=1+\sum_{k=1}^{n-1}k\cdot k!$
###### Proof.

We first consider two degenerate cases. When $n=0$ or $n=1$, 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 $0!=1$ or $1!=1$, which is correct.

Next, assume that $n>1$. Note that

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

hence, we have a telescoping sum:

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

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

###### Theorem 2.

If $d_{m}\ldots d_{2}d_{1}$ is the factoradic representation of a positive integer $n$, then $(d_{m}+1)\,m!>n\geq d_{m}\cdot m!$

###### Proof.

By definition,

 $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\geq d_{m}\cdot m!$. Using the fact that $0\leq d_{k} to bound each term in the sum, we have

 $n\leq d_{m}\cdot m!+\sum_{k=1}^{m-1}k\cdot k!.$

By theorem 1, the right-hand side equals $m!-1$, so we have $n\leq d_{m}\cdot m!+m!-1$, which is the same as saying $(d_{m}+1)\,m!>n$. ∎

###### Theorem 3.

If $d_{m}\ldots d_{2}d_{1}$ and ${d^{\prime}}_{m^{\prime}}\ldots{d^{\prime}}_{2}{d^{\prime}}_{1}$ are distinct factoradic representations with $d_{m}\neq 0$ and ${d^{\prime}}_{m^{\prime}}\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^{\prime}=\sum_{k=1}^{m^{\prime}}{d^{\prime}}_{k}\cdot k!$.

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

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 $n$ such that $n$ has two distinct factoradic representations $d_{m}\ldots d_{2}d_{1}$ and ${d^{\prime}}_{m^{\prime}}\ldots{d^{\prime}}_{2}{d^{\prime}}_{1}$ with $d_{m}\neq 0$ and ${d^{\prime}}_{m^{\prime}}\neq 0$. By the conclusion of the previous paragraph, we must have $m=m^{\prime}$. By theorem 2, we must have $d_{m}={d^{\prime}}_{m}$. Let $m_{1}$ be the chosen such that $d_{m_{1}}\neq 0$ but $d_{m_{1}+1}=\cdots=d_{m-1}=0$ and let $m_{2}$ be the chosen such that ${d^{\prime}}_{m_{2}}\neq 0$ but ${d^{\prime}}_{m_{2}+1}=\cdots={d^{\prime}}_{m-1}=0$. Then $d_{m_{1}}\ldots d_{2}d_{1}$ and ${d^{\prime}}_{m_{2}}\ldots{d^{\prime}}_{2}{d^{\prime}}_{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 $n$ is the smallest number with this property. ∎

Title unambiguity of factorial base representation UnambiguityOfFactorialBaseRepresentation 2013-03-22 16:38:35 2013-03-22 16:38:35 rspuzio (6075) rspuzio (6075) 14 rspuzio (6075) Definition msc 11A63 UniquenessOfDigitalRepresentation