|
|
|
Viewing Version
7
of
'unambiguity of factorial base representation'
|
[ view 'unambiguity of factorial base representation'
|
back to history
]
| Title of object: |
unambiguity of factorial base representation |
| Canonical Name: |
UnambiguityOfFactorialBaseRepresentation |
| Type: |
Definition |
| Created on: |
2007-01-30 01:59:43 |
| Modified on: |
2007-01-31 13:31:53 |
| Classification: |
msc:11A63 |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\newtheorem{theorem}{Theorem} |
Content:
\begin{theorem}
For all positive integers $n$, it is the case that
\[n! = 1 + \sum_{k = 1}^{n - 1} k \cdot k!\]
\end{theorem}
\begin{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!\]
\end {proof}
\begin{theorem}
If $d_m \ldots d_2 d_1$ is the factoradic representation of
a positive integer $n$ and the leading digit $d_m$ is not zero,
then $(m+1)! > n \ge m!$.
\end{theorem}
\begin{proof}
By definition,
\[ n = \sum_{k=1}^m d_k \cdot k! .\]
Since $d_m > 0$, we have $d_m \ge 1$, so $n \ge d_m \cdot m! \ge m!$.
Using the fact that $0 \le d_k < k$ to bound each term in the sum,
we have
\[ n \le \sum_{k=1}^m k \cdot k! \]
By theorem one, the right-hand side equals $(m+1)!$, so $n \le (m+1)!
- 1$, which is the same as saying $(m+1)!$.
\end{proof}
\begin{theorem}
If $d_m \ldots d_2 d_1$ and ${d'}_{m'} \ldots {d'}_2 {d'}_1$ are
distinct factoradic representations with $d_m \neq 0$ and ${d'}_{m'}
\neq 0$ (i.e. not padded with leading zeros), then they denote
distinct integers.
\end{theorem}
\begin{proof}
Let $n = \sum_{k=1}^m d_k \cdot k!$ and let $n' = \sum_{k=1}^{m'}
{d'}_k \cdot k!$.
Suppose that $m$ and $m'$ are distinct. Without loss of generality,
we may assume that $m < m'$. Then, $(m+1)! \le {m'}!$. By theorem 2,
we have $n < (m + 1)!$ and ${m'}! \le n'$. Hence, $n < n'$, so $n$
does not equal $n'$.
(to be continued (of course, we leave at the cliffhanger :) ))
\end{proof} |
|
|
|
|
|
