unambiguity of factorial base representation
Theorem 1.
For all positive integers , it is the case that
Proof.
We first consider two degenerate cases. When or , 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 or , which is correct.
Next, assume that . Note that
hence, we have a telescoping sum:
Adding 1, we conclude that
∎
Theorem 2.
If is the factoradic representation of a positive integer , then
Proof.
Theorem 3.
If and are distinct factoradic representations with and (i.e. not padded with leading zeros), then they denote distinct integers.
Proof.
Let and let .
Suppose that and are distinct. Without loss of generality, we may assume that . Then, . By theorem 2, we have and . Because , we have . Because , 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 and
with and . By the conclusion
of the
previous paragraph, we must have . By theorem 2, we must have
. Let be the chosen such
that but and let
be the chosen such that but . Then and would be distinct factoradic representations of
whose leading digits are not zero but this would
contradict the assumption
that 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 |