I recently examined the binomial coefficient $\binom{\frac{1}{2}}{k}$ and found that the denominator was always a power of two. The same is true of $\binom{\frac{1}{3}}{k}$, where the denominator is always a power of three. While the first proof was simple, the case of $\frac{1}{3}$ was messy and involved counting the powers of 3 in the numerator and denominator. The case of $\frac{1}{p}$ for prime $p$ can be done in the same bashy way. Is it possible there is a more elegant proof?

  • 5
    $\begingroup$ $$\binom{\frac1{p}}{k}=\frac{(-1)^k}{k!}\prod_{j=0}^{k-1} \left(j-\frac1{p}\right)$$ might be a useful identity... $\endgroup$ – J. M. is a poor mathematician Jul 9 '12 at 16:01
  • $\begingroup$ This identity leads to a bashy algebraic solution. I was looking for something more elegant and "combinatorial", unless I'm missing some algebra trick that makes that identity easy to work with. $\endgroup$ – Timothy Salus Jul 9 '12 at 16:31
  • $\begingroup$ Nevermind I see how that identity can be used elegantly after more thought. Thanks! I'm new to the site; is it generally advised for me to post a full solution if I have discovered one? $\endgroup$ – Timothy Salus Jul 9 '12 at 16:42
  • $\begingroup$ Answering your own question is warmly encouraged here at StackExchange; there is even a "Self-Learner" badge. $\endgroup$ – J. M. is a poor mathematician Jul 9 '12 at 16:52
  • $\begingroup$ You can check too that $(1+4x)^{1/2}$ has integral coefficients. $\endgroup$ – Lubin Jul 9 '12 at 22:25

Using the identity $$\binom{\frac{1}{p}}{k}=\frac{(-1)^k}{k!}\prod_{j=0}^{k-1} \left({j-\frac{1}{p}}\right)$$ I found a fairly simple proof for why the denominator of this binomial coefficient is always a power of $p$.

Let $p^a$ be the highest power of $p$ that divides $k!$. Then, $$\prod_{j=0}^{k-1}\left({j-\frac{1}{p}}\right) \equiv \prod_{j=0}^{k-1}({j+n}) \equiv 0 \pmod{ \frac{k!}{p^a}}$$ for some $n \equiv \frac{1}{p} \pmod {\frac{k!}{p^a}}$, with congruence to 0 resulting from the fact that $k!$ always divides a product of $k$ consecutive integers. Thus we have $$\prod_{j=0}^{k-1}\left({j-\frac{1}{p}}\right)=\left(\frac{k!}{p^a}\right)z$$ for $z \in \mathbb{Z}$. Substituting then provides,

$$\binom{\frac{1}{p}}{k}=\frac{(-1)^k}{k!}\left(\frac{k!}{p^a}\right)z=\frac{(-1)^kz}{p^a}$$ completing the proof.


Here’s a purely conceptual proof, more advanced, that has the advantage of involving no computation and no induction:

  1. Let $N$ be a positive number, and let $P_N(t)$ be the polynomial function that tells you the coefficient of $x^N$ in $(1+x)^t$. You know that $P_N$ has rational coefficients, and takes integer values when $t$ is evaluated to a positive integer.
  2. Now consider any prime number $q$. The polynomial $P_N$ has its coefficients in the field ${\mathbb{Q}}_q$ of $q$-adic numbers, is continuous, and takes values in the $q$-adic integers ${\mathbb{Z}}_q$ whenever $t$ is evaluated to a positive integer.
  3. But any rational number without $q$ in its denominator is a $q$-adic integer, so $q$-adically approximable by ordinary integers, and in fact by positive integers. Thus if $\alpha$ is a rational with no $q$ in its denomiator, we get $P_N(\alpha)\in{\mathbb{Z}}_q$, by continuity of $P_N$.
  4. In particular, the coefficients of $(1+x)^{1/p}$ are rational numbers that are in ${\mathbb{Z}}_q$ for each $q\ne p$: the only denominators are powers of $p$.

A more advanced argument allows you to say just how divisible by $p$ the denominators of the coefficients of $(1+x)^{1/p}$ will be, but that’s a story for another day.

  • $\begingroup$ Unfortunately I have just about zero experience with the $p$-adic integers, but thank you for your answer! $\endgroup$ – Timothy Salus Jul 9 '12 at 22:39

Observe \begin{align} (1 + x)^{1/p} = 1 + \frac{x}{p} - \frac{1-p}{2p^{2}} x^{2} + \frac{1 - 3p + 2p^{2}}{6 p^{3}} x^{3} - \cdots \end{align}

  • $\begingroup$ See J.M.'s comment for the exact form of the coefficients. $\endgroup$ – user02138 Jul 9 '12 at 16:05

Firstly, note the definition of binomial coefficients with arbitrary real upper co-efficient:

$${r\choose k}=\begin{cases}\frac{r^{\underline{k}}}{k!} & k\in\mathbb{Z}^{*} \\ 0 & k\in\mathbb{Z}^{-}\end{cases}$$

Where $r^{\underline{k}}=r(r-1)(r-2)\cdots(r-k+1)$ is the falling factorial.

Now for your problem, let $r=\frac{1}{x},\forall x\in\mathbb{N}$. It is fairly evident that the bottom will contain at least one power of $x$, whilst the top will contain no powers of $x$, therefore $x$ will divide the denominator of ${r \choose k}$. Which is what you are trying to prove.

  • $\begingroup$ It's clear that $x$ divides the denominator. But what we want to prove is that the denominator is always just a power of $x$. $\endgroup$ – Timothy Salus Jul 9 '12 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.