$^nC_r=\sum_{i=0}^k a_i\,^kC_i$

Question

$k,r,n$ are positive integer such that $1<k<r<n$. Find $a_i,0\le i\le k$ such that:

$^nC_r=\sum_{i=0}^k a_i\,^kC_i$

Answer 1

To get anywhere here, first we need to relax those constraints a bit. Specifically, there is no reason why $k$ and $r$ should have anything to do with one another, and it's easier to see what happens if they don't. Let's say $0 \leq k,r\leq n$. The answer we get will still apply under the stricter conditions. Also, let's assume that if $r<0$ or $r>n$, then $\binom nr = 0$. It will let us handle all sorts of special cases as part of the general argument.

The first case, $n = k$ is easy. Just from writing it out as $\binom{n}{r} = \sum_{i = 0}^n a_i\binom{n}{i}$, we see directly that $a_r = 1$ and otherwise $a_i = 0$ works.

Now, let's take $k = n-1$. It is, in some books, the defining property of binomial coefficients that $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$. If it isn't, then it's an important identity anyways, so you need to know it and know how to prove it. Once that is done, we have $a_{r-1} = a_{r} = 1$ and all other $a_i = 0$.

Next, let's look at $k = n-2$. What we do is we take the above expression $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$, and we use the same identity on each of the terms on the right-hand side. We then get $$ \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n-2}{r-2} + \binom{n-2}{r-1} + \binom{n-2}{r-1} + \binom{n-2}{r}\\ = \binom{n-2}{r-2} + 2\binom{n-2}{r-1} + \binom{n-2}{r} $$ so in this case, $a_{r-2} = 1, a_{r-1} = 2, a_r = 1$ and for all other $i$, we have $a_i = 0$.

If we do this one more time, we will get $a_{r-3}= 1, a_{r-2} =3, a_{r-1} = 3,a_r = 1$. Does this pattern look familiar to you? A proof by induction, showing that the $a_i$ from two consecutive levels obey a certain identity mentioned earlier in this answer is enough to conclude.

---

Alternative solution: $a_0 = \binom{n}{r}$, and for all other $i$, we have $a_i = 0$.