| Version current |
Version 10 |
| \begin{theorem} |
\begin{theorem} |
| For all positive integers $n$, it is the case that |
For all positive integers $n$, it is the case that |
| \[n! = 1 + \sum_{k = 1}^{n - 1} k \cdot k!\] |
\[n! = 1 + \sum_{k = 1}^{n - 1} k \cdot k!\] |
| \end{theorem} |
\end{theorem} |
|
|
| \begin{proof} |
\begin{proof} |
| We first consider two degenerate cases. When $n=0$ |
We first consider two degenerate cases. When $n=0$ |
| or $n=1$, the sum has no terms because the lower limit |
or $n=1$, the sum has no terms because the lower limit |
| is bigger than the upper limit. By the convention that |
is bigger than the upper limit. By the convention that |
| a sum with no terms equals zero, the equation reduces |
a sum with no terms equals zero, the equation reduces |
| to $0! = 1$ or $1! = 1$, which is correct. |
to $0! = 1$ or $1! = 1$, which is correct. |
|
|
| Next, assume that $n > 1$. Note that |
Next, assume that $n > 1$. Note that |
| \[k \cdot k! = (k + 1) k! - k! = (k + 1)! - k!,\] |
\[k \cdot k! = (k + 1) k! - k! = (k + 1)! - k!,\] |
| hence, we have a telescoping sum: |
hence, we have a telescoping sum: |
| \[\sum_{k = 1}^{n - 1} k \cdot k! = \sum_{k = 1}^{n - 1} |
\[\sum_{k = 1}^{n - 1} k \cdot k! = \sum_{k = 1}^{n - 1} |
| \left( (k + 1)! - k! \right) = n! - 1\] |
\left( (k + 1)! - k! \right) = n! - 1\] |
| Adding 1, we conclude that |
Adding 1, we conclude that |
| \[n! = 1 + \sum_{k = 1}^{n - 1} k \cdot k!\] |
\[n! = 1 + \sum_{k = 1}^{n - 1} k \cdot k!\] |
| \end {proof} |
\end {proof} |
|
|
| \begin{theorem} |
\begin{theorem} |
| If $d_m \ldots d_2 d_1$ is the factoradic representation of |
If $d_m \ldots d_2 d_1$ is the factoradic representation of |
| a positive integer $n$, then $(d_m + 1) \, m! > n \ge d_m |
a positive integer $n$, then $(d_m + 1) \, m! > n \ge d_m |
| \cdot m!$ |
\cdot m!$ |
| \end{theorem} |
\end{theorem} |
|
|
| \begin{proof} |
\begin{proof} |
| By definition, |
By definition, |
| \[ n = d_m \cdot m! + \sum_{k=1}^{m-1} d_k \cdot k! .\] |
\[ 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, |
Since each term of the sum is nonnegative, the sum is positive, |
| hence $n \ge d_m \cdot m!$. Using the fact that $0 \le d_k < k$ |
hence $n \ge d_m \cdot m!$. Using the fact that $0 \le d_k < k$ |
| to bound each term in the sum, we have |
to bound each term in the sum, we have |
| \[ n \le d_m \cdot m! + \sum_{k=1}^{m-1} k \cdot k!.\] |
\[ 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 |
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 |
$n \le d_m \cdot m! + m! - 1$, which is the same as saying |
| $(d_m + 1) \, m! > n$. |
$(d_m + 1) \, m! > n$. |
| \end{proof} |
\end{proof} |
|
|
| \begin{theorem} |
\begin{theorem} |
| If $d_m \ldots d_2 d_1$ and ${d'}_{m'} \ldots {d'}_2 {d'}_1$ are |
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'} |
distinct factoradic representations with $d_m \neq 0$ and ${d'}_{m'} |
| \neq 0$ (i.e. not padded with leading zeros), then they denote |
\neq 0$ (i.e. not padded with leading zeros), then they denote |
| distinct integers. |
distinct integers. |
| \end{theorem} |
\end{theorem} |
|
|
| \begin{proof} |
\begin{proof} |
| Let $n = \sum_{k=1}^m d_k \cdot k!$ and let $n' = \sum_{k=1}^{m'} |
Let $n = \sum_{k=1}^m d_k \cdot k!$ and let $n' = \sum_{k=1}^{m'} |
| {d'}_k \cdot k!$. |
{d'}_k \cdot k!$. |
|
|
| Suppose that $m$ and $m'$ are distinct. Without loss of generality, |
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 may assume that $m < m'$. Then, $(m+1)! \le {m'}!$. By theorem 2, |
| we have $n < (d_m + 1) \, m!$ and $d_{m'} \cdot {m'}! \le n'$. Because |
we have $n < (d_m + 1) \, m!$ and $d_{m'} \cdot {m'}! \le n'$. Because |
| $d_m \le m$, we have $(d_m + 1) \,m! \le (m + 1) \, m! = (m + 1)!$. |
$d_m \le m$, we have $(d_m + 1) \,m! \le (m + 1) \, m! = (m + 1)!$. |
| Because $d_{m'} \neq 0$, we have $n' > {m'}!$. Hence, $n < n'$, so $n$ |
Because $d_{m'} \neq 0$, we have $n' > {m'}!$. Hence, $n < n'$, so $n$ |
| does not equal $n'$. |
does not equal $n'$. |
|
|
|
To complete the proof, we use the method of infinite descent. Assume
|
To complete the prr\oof, we use the method of infinite descent. Assume
|
| that factoradic representations are not unique. Then there must exist |
that factoradic representations are not unique. Then there must exist |
| a least integer $n$ such that $n$ has two distinct factoradic |
a least integer $n$ such that $n$ has two distinct factoradic |
| representations $d_m \ldots d_2 d_1$ and ${d'}_{m'} \ldots {d'}_2 {d'}_1$ |
representations $d_m \ldots d_2 d_1$ and ${d'}_{m'} \ldots {d'}_2 {d'}_1$ |
| with $d_m \neq 0$ and ${d'}_{m'} \neq 0$. By the conclusion of the |
with $d_m \neq 0$ and ${d'}_{m'} \neq 0$. By the conclusion of the |
| previous paragraph, we must have $m = m'$. By theorem 2, we must have |
previous paragraph, we must have $m = m'$. By theorem 2, we must have |
| $d_m = {d'}_m$. Let $m_1$ be the chosen such |
$d_m = {d'}_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 |
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'}_{m_2} \neq 0$ but ${d'}_{m_2 + 1} = |
$m_2$ be the chosen such that ${d'}_{m_2} \neq 0$ but ${d'}_{m_2 + 1} = |
| \cdots = {d'}_{m-1} = 0$. Then $d_{m_1} \ldots d_2 d_1$ and ${d'}_{m_2} |
\cdots = {d'}_{m-1} = 0$. Then $d_{m_1} \ldots d_2 d_1$ and ${d'}_{m_2} |
| \ldots {d'}_2 {d'}_1$ would be distinct factoradic representations of |
\ldots {d'}_2 {d'}_1$ would be distinct factoradic representations of |
| $n - d_m \cdot m!$ whose leading digits are not zero but this would |
$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 |
contradict the assumption that $n$ is the smallest number with this |
| property. |
property. |
| \end{proof} |
\end{proof} |
