So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides:

$$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$

Writing these choice functions in factorial form, I obtain:

$$\frac{(p-1)!}{k!(p-(k+1))!} + \frac{(p-2)!}{(k-1)!(p-(k+1))!} + \cdots + \frac{(p-k)!}{1!(p-(k+1))!} + 1$$

Thus as you can see each term except the last has a $(p-(k+1))!$ factor in its denominator. I've tried some stuff with integer partitions, tried to do some factoring and simplification, etc. But I can't see how to prove that $p$ divides this expression. I'll probably have to use the fact that $p$ is prime somehow, but I'm not sure how. Can anyone help me? Thanks.

Edit: Proof by induction is also a possibility I suppose, but that approach seems awfully complex since changing k changes every term but the last.

  • 1
    $\begingroup$ Perhaps you can use the identity from her here and the fact that $p\mid \binom pk$ for $0<k<p$, see e.g. here. $\endgroup$ – Martin Sleziak Sep 30 '12 at 20:35
  • 1
    $\begingroup$ @Martin: That looks like an answer to me. Why "perhaps"? $\endgroup$ – joriki Sep 30 '12 at 20:38
  • $\begingroup$ @Martin: Thanks I'll look into that. $\endgroup$ – Thoth Sep 30 '12 at 20:39
  • $\begingroup$ @joriki I had the feeling we have an exact duplicate somewhere. (But I might be wrong.) I've posted at least what I found. Anyway, if a duplicate will not be found, I can post a more detailed version of the comment as an answer. (Or someone else can do it. Perhaps even the OP.) It's getting late here, so I don't really have energy to do that now. $\endgroup$ – Martin Sleziak Sep 30 '12 at 20:44
  • $\begingroup$ Related: math.stackexchange.com/questions/833451 $\endgroup$ – punctured dusk Apr 8 '15 at 15:09

$$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1= \sum_{i=0}^k\binom{p-k-1+i}i =\binom pk, $$ and it is well known that a prime $p$ divides all binomial coefficients $\binom pk$ with $k\notin\{0,p\}$ (cf. the Frobenius endomorphism of rings of characteristic $p$). The fact that $\sum_{i=0}^k\binom{n+i}i=\binom{n+k+1}k$ is immediate by recurrence on $k$ from the Pascal's rule, the basic recurrence defining binomial coefficients.

If you prefer combinatorial arguments to algebra: you can understand the summation identity by classifying the $k$-combinations of a $p$-set according to the first element that is not in the $k$-combination (if the very first element of the $p$-set is not in the $k$-combination, then one has a $k$-combination of the remaining $p-1$; if the first element is in the $k$-combination but the second one is not, then $k-1$ of the remaining $p-2$ elements must be chosen to complete the $k$-combination; and so forth, until element $k+1$ which cannot be in the $k$-combination if all values before it are already in, contributing $1$), and you can understand the divisibility $p\mid\binom pk$ by the fact that by cyclically rotating $k$-combinations, one can group them into orbits of $p$ distinct $k$-combinations each.

  • $\begingroup$ Ah! Pascal's Rule setting $1$ = $p-k$ choose $0$, thanks! $\endgroup$ – Thoth Oct 1 '12 at 17:26

Letting $k=p-1$, we find that the expression equals $p$ summands of value $1$ each.

Maybe the problem was not meant to read "for some natural" but rather "for all natural" numbers $1\le k<p$. The statement remains true, once you observer that the sum is simply $p\choose k$. To see this combinatorially, note that you can choose $k$ out of $p$ objects by selecting $r$ with $0\le r \le k$, then take the first $r$ objects, do not take the next object and choose $k-r$ out of the remaing $p-1-r$ objects.

Finally, $p\choose k$ with $0<k<p$ is a multiple of $p$, for example because $p$ divides $p!$ but divides neither $k!$ nor $(p-k)!$. (This is where we need that $p$ is prime),

  • $\begingroup$ Yes you're right I should have put "any". $\endgroup$ – Thoth Sep 30 '12 at 22:00
  • $\begingroup$ Hey Hagen could you show me how that whole thing sums up to p choose k? Thanks. $\endgroup$ – Thoth Sep 30 '12 at 22:18
  • $\begingroup$ @Coco, are you familiar with n-choose-k plus n-choose-(k - 1) equals (n + 1)-choose-k? You start at the right end of the sum and use that repeatedly, working your way to the left. $\endgroup$ – Gerry Myerson Oct 1 '12 at 6:18
  • $\begingroup$ @Cocojambles Do it formally as Gerry suggests or think about the combinatorial proof I gave above. $\endgroup$ – Hagen von Eitzen Oct 1 '12 at 9:36
  • $\begingroup$ @Gerry: Ah! I see, you have to write 1 as $p-k$ choose $0$! Nice thanks. $\endgroup$ – Thoth Oct 1 '12 at 17:22

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.