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 limitis bigger than the upper limit. By the convention thata sum with no terms equals zero, the equation reducesto $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 ofa 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}}$ aredistinct 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 denotedistinct 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. Assumethat factoradic representations are not unique. Then there must exista least integer $n$ such that $n$ has two distinct factoradicrepresentations $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 theprevious paragraph, we must have $m=m^{\prime }$. By theorem 2, we must have$d_m=d^{\prime }{}_m$. Let $m_1$ be the chosen suchthat $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 wouldcontradict the assumption that $n$ is the smallest number with thisproperty.∎