Alternative Proof for ${n\choose k}$ is integer

Question

I have seen different type of induction proofs on this case, but trying an alternative approach I tried Induction to show that ${n\choose k}$ in binomial coefficient is an integer, where both n and k are non-negative integers.

Base case: For k = 0, ${n\choose 0}$ = 1, and is integer.

Inductive Hypothesis: For k= n-1, Assume ${n\choose n-1}$ is integer. (That's not even assumption but a fact, in fact.)

Finally, induction: For k = n, ${n\choose n}$ is integer because it's 1.

Is this a proof? Is this a thing? What is it?

Answer 1

I see a proof of the following:

Fom completely unconstrained $n$, so for instance, complex numbers. Try it with $n = 1/2$, which shows up in the binomial expansion for the square root, $\sqrt{1+x} = \sum_{k \geq 0} \binom{1/2}{k} x^k$.

• $\binom{n}{0}$ is an integer because you say so. Not even so much as a "$\binom{n}{0} = 1$" without justification. At the very least, you should apply its definition so the reader can inspect that expression to validate your claim: "$\binom{n}{0} = \frac{n!}{0!(n-0)!} = 1$".
• $\binom{n}{n-1}$ is an integer because you say so, without even a pretension of proof. Perhaps "$\binom{n}{n-1} = \frac{n!}{1!(n-1)!} = n$" would be more convincing. This also highlights that you need to assert "$n$ is an integer" before starting these cases.
• $\binom{n}{n}$ is an integer because you say it is $1$. More convincing: "$\binom{n}{n} = \frac{n!}{n!0!} = 1$".

There is nothing here that shows $\binom{3}{1}$ is an integer.

Answer 2

I recommend you first try inducting on $n$ rather than $k$, since each $n$ has only finitely many $k$ to check. To prove $k!|\frac{n!}{(n-k)!}=\prod_{j=0}^{k-1}(n-j)$ for $n\ge k$, note $n=k$ obtains the product as $\prod_{j=0}^{k-1}(k-j)=k!$, while$$\prod_{j=0}^{k-1}(m+1-j)-\prod_{j=0}^{k-1}(m-j)=\prod_{i=m-k+2}^{m+1}i-\prod_{i=m-k+1}^mi=k\prod_{i=m-k+2}^mi=k\frac{m!}{(m-k+1)!}.$$The inductive step works if this is a multiple of $k!$, or equivalently if $(k-1)!|\frac{m!}{(m-k+1)!}$. This tells us we can use what's called double induction:

• $k=0$ works since $0!=1|1=\frac{n!}{(n-0)!}$;
• If $k=l$ works for all $n$, $k=l+1$ works for $n=l+1$ by similar logic, while larger $n$ follow by the above inductvie step.