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?)
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$