## You are here

Homeunambiguity of factorial base representation

## Primary tabs

# 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}\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}<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<m^{{\prime}}$. 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<n^{{\prime}}$, 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. ∎

## Mathematics Subject Classification

11A63*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections