Problem 92 *

Define a_1 = 1 and for n > 1, define a_n = n(a_1 + \ldots + a_{n - 1}).

Show that for every n \equiv 0 \pmod 2, a_n is divisible by n!.

Also, find all n \equiv 1 \pmod 2 such that a_n \equiv 0 \pmod {n!}.

[originally posted by Mladenov on TSR]

Conjecture: a_n=\frac{1}{2}n\cdot n!

Proof:

True for a_2 and assume true for some n=k.

a_k=k(a_1+...+a_{k-1})=\frac{1}{2}k\cdot k!
\Rightarrow a_1+...+a_{k-1}=\frac{1}{2}k!

a_{k+1}=(k+1)(a_1+...+a_{k-1}+a_k)
\hspace{1cm}=(k+1)(\frac{1}{2}k!+\frac{1}{2}k\cdot k!)
\hspace{1cm}=\frac{1}{2}(k+1)(k+1)!

\therefore a_n=\frac{1}{2}n\cdot n! for all n\geq 2

So now our question is just to show that for even n, n!\mid\frac{1}{2}n\cdot n!

This is fairly straightforward because \frac{\frac{1}{2}n\cdot n!}{n!}=\frac{1}{2}n which is an integer for even n.

Now for the second part: for which odd n does n\mid \frac{1}{2}n\cdot n!?. This is again pretty straightforward because \frac{\frac{1}{2}n\cdot n!}{n!}=\frac{1}{2}n which is not an integer for any odd n. However, recall that our induction was for n\geq 2 so we need to check a_1. a_1=1=1!\; \therefore the only odd n is n=1.

3 Likes