Prove this induction problem

Question

Show that every positive integer $N$ less than or equal to $n$ factorial, is the sum of at most $n$ distinct positive integers, each of which divides $n!$.

Answer 1

Step 1:

Show that the statement holds for $n=1$. For this value of $n$ we have $1!=1$, and thus every positive integer less than or equal to $1!$ is the set $\{1\}$. Since $n=1$ we must find a sum of at most one positive integer which divides $1!$ and adds up to each of the numbers in our given set, and indeed we have

$$\sum_{i=1}^11=1$$

This proves the case for $n=1$.

The second step is to assume that the proposition is true for $n=k\ge 1$. We now adopt this assumption, namely that every positive integer less than or equal to $n!=k!\ge 1!$ is the sum of at most $n=k$ distinct positive integers, each of which divides $n!=k!$.

The last step is to prove that this assumption leads to the conclusion that the proposition holds for the case $n=k+1$. One way to start is to take a number which is considered "arbitrary" from the range associated with this case; another approach would be to do a secondary induction over the set of numbers associated with this case.

Answer 2

We deal with the induction step. Suppose that the result holds when $n=k$. We show the result holds when $n=k+1$. So we want to show that every positive integer $N\le (k+1)!$ is representable as a sum $y_1+\cdots +y_t$, where $t\le k+1$, and where the $y_j$ are distinct divisors of $(k+1)!$.

If $N$ is divisible by $k+1$, we are essentially finished. For we have $\frac{N}{k+1}\le k!$. Thus, using the induction hypothesis, we can represent $\frac{N}{k+1}$ as $\frac{N}{k+1}=x_1+\cdots +x_t$, where $t\le k$ and the $x_j$ are distinct divisors of $k!$. Let $y_j=(k+1)x_j$. Then $N=y_1+\cdots +y_t$, and the $y_j$ are distinct divisors of $(k+1)!$.

Now suppose that $N$ is not divisible by $k+1$. Then $N$ leaves some remainder $r$ on division by $k+1$, where $1\le r\le k$.

Then $N-r$ is divisible by $n+1$. So again by the induction hypothesis there exists a $s\le k$, and distinct divisors $x_1,\dots, x_s$ of $k!$, such that $\frac{N-r}{k+1}=x_1+\cdots +x_s$.

Let $y_j=(k+1)x_j$ for $1\le j\le s$, and let $y_{s+1}=r$. Then $s+1\le k+1$, and $N=y_1+\cdots+y_s+y_{s+1}$.

For $1\le j\le s$, the $x_j$ are distinct divisors of $k!$. Thus the $y_j$ are distinct divisors of $(k+1)!$. Since $y_{s+1}=r\le k$, it follows that $y_{s+1}$ is also a divisor of $(k+1)!$. Finally, $y_{s+1}$ is not equal to any $y_j$ with $j\le s$, since $y_{s+1}$ is not divisible by $k+1$, but the others are.

This completes the induction step.