$n!\sum_{k=1}^n \frac{a_{k}}{k!}$ is always integer.

Question

$\displaystyle n!\sum_{k=1}^n \frac{a_{k}}{k!}\in \mathbb{Z}$

where $n,a_k$ and $k$ are integers. I know the proof by induction. Is there any other technique to prove it?

Thank you.

Answer 1

I think this is trivial but perhaps I'm missing something:

$$\frac{n!}{k!}\;\;\text{is always an integer for any}\;\;0\le k\le n$$

so your sum is a sum of integers...

Answer 2

This seem long for a comment, so I will put it here. I am not sure that you can actually prove things like this without the power of induction. The reason is if we start from first principles, (let's say the basic rules of algebra). I will begin by giving the proof, then analyze the steps. We start with the sum, $$n!(\frac{a_1}{1!}+\frac{a_2}{2!}+\cdots\frac{a_n}{n!}). $$

The first step is to distribute the $n!$, but notice that we need to know that we can distribute things of the form, $$A:k(b_1+b_2+\cdots b_n),$$ but normally, the basic rules of algebra, (called the field axioms) usually only tell us that we may perform distributions of the form, $$B:k(b_1+b_2)=kb_1+b_2.$$ On must also define what $(b_1+b_2+\cdots b_n)$ is. But we may define recursively to be $$(b_1+\cdots b_{n-1})+b_n.$$ We may then prove A using B and induction. After proving A, we may apply it to our situation. As answered in DonAntonio's post, we need two more facts:

C: If $0\leq k\leq n$, then $\frac{n!}{k!}$, is an integer.

D: If $b_1,b_2,\cdots, b_n$ are integers, so is $b_1+b_2+\cdots b_n$.

Both if these may be proved by induction, and either is particularly difficult.

So to your question, "Is there any other technique to prove it", I would say that you seem to actually need three inductions, but they may be suppressed as "obvious lemmas", that seem to need induction.

So a new question might be "Can we prove A without induction".