$(1+z)^s$

Sum[Gamma[1 + x]/(Gamma[1 + x - y] Gamma[1 + y])z^y, {y, 0, \[Infinity]}]

For natural numbers $n\ge{k}$ we get

${n\choose{k}} = \dfrac{1}{k!}\dfrac{n!}{(n-k)!}$

${m\choose{m}} = 1$

${m\choose{0}} = 1$

${n\choose{k}} = {n\choose{k-1}} + {n-1\choose{k-1}}$

From this it's also clear that ${n\choose{k}}$ is a sum of 1's, i.e. an integer.

(*Random generalization of linear such recursive schemes*)

f[m_, 0] = a[m];
f[0, m_] = b[m];
f[m_, m_] = c[m];

f[n_, k_] := A*f[n, k - 1] + B*f[n - 1, k] + C*f[n - 1, k - 1]

Table[{n, k, f[n, k] // sexy}, {n, 1, 4}, {k, 1, 4}] // TableForm

Wikipedia: Binomial coefficient

Gamma function