1

I have a question from Putnam and Beyond. It says that

"...for some positive integers m and k, the binomial coefficient $m \choose k$ is a linear combination of $m^k$, $m \choose {k−1}$ , $\dots$ , $m\choose 0$ whose coefficients do not depend on m. In this linear combination the coefficient of $m^k$ is $\frac{1}{k!}$."

I honestly have no idea what this means - I've been bashing my head against it, but I don't really understand it at all. How can we express $\frac{m!}{(m-k!)(k!)}$ as a linear combination whose coefficients does not depend on $m$? I already tried the standard $(x+y)^m$ trick, but that doesn't really yield any fruitful results.

EDIT: I just thought aboutg $m \choose k$ as a polynomial (namely $m(m-1)(m-2)...(m-(k-1))/k!$), but the coefficients still depend on $m$.

user124577
  • 309

1 Answers1

5

The statement in symbols is that there is some collection of scalars $a_0, a_1, \dots, a_k$ (which may depend on $k$ but not $m$) such that

$$\binom mk = a_km^k + a_{k-1}\binom m{k-1} + \cdots + a_1\binom m1 + a_0\binom m0,$$

and moreover that $a_k=1/k!$ One way to prove this is by induction, using basic linear algebra facts applied to the vector space of polynomials up to degree $d$.

Eric Stucky
  • 12,758
  • 3
  • 38
  • 69
  • Can you explain which linear algebra facts to use in the proof? I (think) I can think of a proof that doesn't use linear algebra, but I'm probably missing something. – user124577 Nov 10 '14 at 04:29
  • It may not need linear algebra (I did not go through the proof myself). I was thinking that spanning sets of size $d+1$ are always bases. – Eric Stucky Nov 10 '14 at 04:32