Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
5  
$$\binom{\frac1{p}}{k}=\frac{(-1)^k}{k!}\prod_{j=0}^{k-1} \left(j-\frac1{p}\right)$$ might be a useful identity... –  J. M. Jul 9 '12 at 16:01
    
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. –  Timothy Salus Jul 9 '12 at 16:31
    
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? –  Timothy Salus Jul 9 '12 at 16:42
    
Answering your own question is warmly encouraged here at StackExchange; there is even a "Self-Learner" badge. –  J. M. Jul 9 '12 at 16:52
    
You can check too that $(1+4x)^{1/2}$ has integral coefficients. –  Lubin Jul 9 '12 at 22:25
add comment

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
Well done.$\phantom{}$ –  J. M. Jul 10 '12 at 4:57
add comment

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}

share|improve this answer
    
See J.M.'s comment for the exact form of the coefficients. –  user02138 Jul 9 '12 at 16:05
add comment

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.

share|improve this answer
    
Unfortunately I have just about zero experience with the $p$-adic integers, but thank you for your answer! –  Timothy Salus Jul 9 '12 at 22:39
add comment

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.

share|improve this answer
    
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$. –  Timothy Salus Jul 9 '12 at 16:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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