Count the subsets of cardinality k + 1 of \{0, 1, \dots, n\} in two ways. There are \binom{n+1}{k+1} of them. On the other hand, split them according to whether they contain the distinguished element n: deleting n is a bijection between those that do and the subsets of cardinality k of \{0, 1, \dots, n-1\}, of which there are \binom{n}{k}, while those that do not are exactly the subsets of cardinality k + 1 of \{0, 1, \dots, n-1\}, of which there are \binom{n}{k+1}.

Compare the coefficients of X^{k+1} on the two sides of (1 + X)^{n+1} = (1 + X)(1 + X)^n. By the binomial theorem, which is proved by induction on n, the coefficient of X^j in (1 + X)^n is \binom{n}{j}. So the left-hand side contributes \binom{n+1}{k+1}, while multiplying by 1 + X adds a copy of the coefficients shifted by one, making the right-hand side \binom{n}{k+1} + \binom{n}{k}.

Induct on n. The successor step adds the last summand and then uses Pascal's identity at the end of the diagonal.

Count the subsets of cardinality k + 1 of \{0, 1, \dots, n + k\} in two ways. There are \binom{n+k+1}{k+1} of them. On the other hand, sort them by their largest element m, which ranges over k, k+1, \dots, n+k: deleting m is a bijection between the subsets with largest element m and the subsets of cardinality k of \{0, 1, \dots, m-1\}, of which there are \binom{m}{k}. Summing over m = i + k for 0 \le i \le n gives the left-hand side.