2

It's well-known and easy to show that

$\binom{k}{n} = \frac{k}{n}\binom{k-1}{n-1}$.

Also, I've come across the formula

$\binom{k}{n}=A\binom{k-1}{n-1}+B\binom{k-2}{n-2}$,

where $A$ and $B$ are coefficients that depend on $n$ and $k$ (and are easily determined). I wonder if anyone knows whether there exists a general (simple) formula that links a binomial coefficient to its diagonal "predecessors" in the form

$\binom{k}{n}=\sum_{i=1}^M A_i\binom{k-i}{n-i}$,

for arbitrary $M$.

(Of course, such a representation will always exist, but does there exist a simple formula where the coefficients $A_i$ can explicitly be determined?)

mathse
  • 2,438
  • 12
  • 18

1 Answers1

2

I am assuming you want the $A_i >0$. Suppose $k > n$, you can start from your first identity $${k \choose n} = \frac{k}{n}{k-1\choose n-1} = \left(\frac{k}{n} -1\right){k-1\choose n-1} + {k-1\choose n-1}$$ And of course $k/n - 1 > 0$ by our assumption that $k > n$. Now apply the same identity to ${k-1\choose n-1}$ to obtain $$ {k \choose n} = \left(\frac{k}{n} -1\right){k-1\choose n-1} + \frac{k-1}{n-1}{k-2 \choose n-2} $$ You can clearly go on with this process as much as you want (finite) and you will end up with $$ {k \choose n} = \left[\sum_{i=1}^{M-1} \left(\frac{k-i+1}{n-i+1} - 1 \right){k-i \choose n -i}\right] + \frac{k-M+1}{n-M+1}{k-M \choose n-M}$$ And all the $A_i$ there are clearly $>0$. For $k = n$, you can just take $A_i = 1/M$

alejopelaez
  • 2,707