5
$\begingroup$

So I'm trying to prove that for any natural number $1\leq k$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
    Perhaps you can use the identity from her [here](http://math.stackexchange.com/questions/74844/induction-proof-concerning-a-sum-of-binomial-coefficients) and the fact that $p\mid \binom pk$ for $0, see e.g. [here](http://math.stackexchange.com/questions/147443/conceptual-proof-that-p-choose-k-1-k-p-is-divisible-by-p-when-p-is).2012-09-30
  • 1
    @Martin: That looks like an answer to me. Why "perhaps"?2012-09-30
  • 0
    @Martin: Thanks I'll look into that.2012-09-30
  • 0
    @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.2012-09-30
  • 0
    Related: http://math.stackexchange.com/questions/8334512015-04-08

2 Answers 2

5

$$\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.

  • 0
    Ah! Pascal's Rule setting $1$ = $p-k$ choose $0$, thanks!2012-10-01
2

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. 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 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),

  • 0
    Yes you're right I should have put "any".2012-09-30
  • 0
    Hey Hagen could you show me how that whole thing sums up to p choose k? Thanks.2012-09-30
  • 0
    @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.2012-10-01
  • 0
    @Cocojambles Do it formally as Gerry suggests or think about the combinatorial proof I gave above.2012-10-01
  • 0
    @Gerry: Ah! I see, you have to write 1 as $p-k$ choose $0$! Nice thanks.2012-10-01
  • 0
    Thank you for your explanation Hagen =] +1.2012-10-01