Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements left to choose from) or it is not (resulting in $k$ elements). We can then take either of the two terms in the identity and apply the same reasoning so that it becomes $n \choose k$ = $n-2 \choose k-2$ + $n-2 \choose k-1$ + $n-1 \choose k$. In general then the identity becomes something like:
$n \choose k$ = $\sum_s$$\sum_{k}$$n-s \choose k-s^{\lfloor k \rfloor}$
I am not quite sure how to expand this properly. What would be the best way to write this expansion, and are there any interesting applications (maybe to binary trees) that comes from this?
$${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} = {n-1 \choose k-1}+{n-2 \choose k-1}+{n-2 \choose k} = ... =\sum_{i=k-1}^{n-1} {i \choose k-1}.$$ An application would be using this to compute $\sum\limits_{i=a}^b i^k$. Or one can keep iterate the other term and get $${n \choose k} = \sum_{i=0}^k {n-1-i \choose k-i}.$$ However, these two representations are the two sides of the same coin. Start from $${n \choose k} = {n \choose n-k},$$ and apply the first expansion, we obtain $${n \choose n-k}=\sum_{i=n-k-1}^{n-1} {i \choose n-k-1}=\sum_{i=0}^k {n-1-i \choose n-k-1}=\sum_{i=0}^k {n-1-i \choose k-i},$$ namely the second expansion.