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

Adding 1, we conclude that

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

∎

Theorem 2.

If $d_m\mathit{}\mathrm{\dots }\mathit{}{d}_{\mathrm{2}}\mathit{}{d}_{\mathrm{1}}$ is the factoradic representation of a positive integer $n$, then $\mathrm{(}{d}_m\mathrm{+}\mathrm{1}\mathrm{)}\mathit{}m\mathrm{!}\mathrm{>}n\mathrm{\ge }{d}_m\mathrm{\cdot }m\mathrm{!}$

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\ge d_m\cdot m!$. Using the fact that to bound each term in the sum, we have

$$n\le 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\le d_m\cdot m!+m!-1$, which is the same as saying $(d_m+1)m!>n$. ∎

Theorem 3.

If $d_m\mathit{}\mathrm{\dots }\mathit{}{d}_{\mathrm{2}}\mathit{}{d}_{\mathrm{1}}$ and $d^{\mathrm{\prime }}{}_{m^{\mathrm{\prime }}}\mathit{}\mathrm{\dots }\mathit{}d^{\mathrm{\prime }}{}_{\mathrm{2}}\mathit{}d^{\mathrm{\prime }}{}_{\mathrm{1}}$ are distinct factoradic representations with $d_m\mathrm{\ne }\mathrm{0}$ and $d^{\mathrm{\prime }}{}_{m^{\mathrm{\prime }}}\mathrm{\ne }\mathrm{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 . Then, $(m+1)!\le m^{\prime }!$. By theorem 2, we have and $d_{m^{\prime }}\cdot m^{\prime }!\le n^{\prime }$. Because $d_m\le m$, we have $(d_m+1)m!\le (m+1)m!=(m+1)!$. Because $d_{m^{\prime }}\ne 0$, we have $n^{\prime }>m^{\prime }!$. Hence, , 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\mathrm{\dots }{d}_2{d}_1$ and $d^{\prime }{}_{m^{\prime }}\mathrm{\dots }d^{\prime }{}_{2}d^{\prime }{}_1$ with $d_m\ne 0$ and $d^{\prime }{}_{m^{\prime }}\ne 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}\ne 0$ but $d_{m_1+1}=\mathrm{\cdots }=d_{m-1}=0$ and let $m_2$ be the chosen such that $d^{\prime }{}_{m_2}\ne 0$ but $d^{\prime }{}_{m_2+1}=\mathrm{\cdots }=d^{\prime }{}_{m-1}=0$. Then $d_{m_1}\mathrm{\dots }{d}_2{d}_1$ and $d^{\prime }{}_{m_2}\mathrm{\dots }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
Canonical name	UnambiguityOfFactorialBaseRepresentation
Date of creation	2013-03-22 16:38:35
Last modified on	2013-03-22 16:38:35
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	14
Author	rspuzio (6075)
Entry type	Definition
Classification	msc 11A63
Related topic	UniquenessOfDigitalRepresentation