I thought Wikipedia had a really elegant proof by induction of the binomial theorem. However, I wondered if the reasoning made at the line marked by (*) below is acceptable.
When $j = 0$, $k = n + 1$, so the left-hand side is the coefficient of the term $x^0y^{n + 1}$, but the right-hand side indicates that this coefficient is the sum of the coefficients of the terms $x^{-1}y^{n + 1}$ and $x^0y^n$, which doesn't seem to make sense. I would consider the case where $j = 0$ separately, which certainly turns out to be true, and only use the $(*)$ equality statement for $j \geq 1$, but I might be missing something. Please advise!
Thank you very much!
When $n = 0$, both sides equal $1$, since $x^0 = 1$ and $\binom{0}{0}=1$. Now suppose that the equality holds for a given $n$; we will prove it for $n + 1$. For $j, k \geq 0$, let $[f(x, y)]_{j,k}$ denote the coefficient of $x^jy^k$ in the polynomial $f(x, y)$. By the inductive hypothesis, $(x + y)^n$ is a polynomial in $x$ and $y$ such that $[(x + y)^n]_{j,k}$ is $\binom{n}{k}$ if $j + k = n$, and $0$ otherwise. The identity
$(x+y)^{n+1} = x(x+y)^n + y(x+y)^n$
shows that $(x + y)^{n+1}$ is also a polynomial in $x$ and $y$, and
$[(x+y)^{n+1}]_{j,k} = [(x+y)^n]_{j-1,k} + [(x+y)^n]_{j,k-1}$ $\quad\quad\quad\quad (*)$
since if $j + k = n + 1$, then $(j - 1) + k = n$ and $j + (k - 1) = > n$. Now, the right hand side is
$\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k},$
by Pascal's identity. On the other hand, if $j + k \neq n + 1$, then $(j - 1) + k \neq n$ and $j + (k - 1) \neq n$, so we get $0 + 0 = 0$. Thus
$(x+y)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} x^{n+1-k} y^k,$
which is the inductive hypothesis with $n + 1$ substituted for $n$ and so completes the inductive step.