The problem was to show that the binomial coefficient $\binom{2n}{n}$ is divisible by $n+1$.
Solution
Let $$C = \dfrac{\binom{2n}{n}}{n+1} = \dfrac{2n!}{n! (n+1)!}$$
$C$ is actually a well known number, it is called a Catalan Number and has numerous combinatorial interpretations. Picking any one such would prove that $C$ is an integer.
But since this is an easy puzzle we will give a short proof.
Now
$$(n+1)C = \dfrac{2n!}{n! n!} = \binom{2n}{n}$$
and
$$nC = \dfrac{2n!}{(n-1)! (n+1)!} = \binom{2n}{n+1}$$
Thus $C = (n+1)C - nC$ is the difference of two binomial coefficients, and is thus an integer.
We can also phrase this as a consquence of:
If $r$ is a rational and $a,b$ are two relatively prime integers such that both $ar$ and $br$ are integers, then $r$ is also an integer.
Solution
Let $$C = \dfrac{\binom{2n}{n}}{n+1} = \dfrac{2n!}{n! (n+1)!}$$
$C$ is actually a well known number, it is called a Catalan Number and has numerous combinatorial interpretations. Picking any one such would prove that $C$ is an integer.
But since this is an easy puzzle we will give a short proof.
Now
$$(n+1)C = \dfrac{2n!}{n! n!} = \binom{2n}{n}$$
and
$$nC = \dfrac{2n!}{(n-1)! (n+1)!} = \binom{2n}{n+1}$$
Thus $C = (n+1)C - nC$ is the difference of two binomial coefficients, and is thus an integer.
We can also phrase this as a consquence of:
If $r$ is a rational and $a,b$ are two relatively prime integers such that both $ar$ and $br$ are integers, then $r$ is also an integer.
No comments:
Post a Comment