Proving $(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} x^k y^{n-k}$ I'm reading Serge Lang's 'Analysis I', and there's a problem I cannot figure out how to prove:

Problem: Prove by induction that $$(x+y)^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^k y^{n-k} . $$

Attempt at proof : I established the base case, which is easily verified. Now I want to prove the inductive step. So assume the assertion holds for $n \geq 1$, and we want to show it also holds for $n + 1$. So we have to proof that: $$(x+y)^{n+1} = \sum_{k=0}^{n+1} \begin{pmatrix} n+1 \\ k \end{pmatrix} x^k y^{n+1-k} . $$
I started with the the LHS and applied the induction hypothesis:
\begin{align*} (x+y)^{n+1} &= (x+y)^n (x+y) \\ & = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^k y^{n-k} (x+y) \\ &= \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^{k+1} y^{n-k} + \sum_{k=0}^n  \begin{pmatrix} n \\ k \end{pmatrix} x^k y^{n-k+1} \\ &= \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} \bigg[ x^{k+1} y^{n-k} + x^k y^{n-k+1} \bigg] \end{align*} Now I don't know how to proceed. Any help would be appreciated! 

The best way to think of the inductive step is to multiply the sum by $(x+y)$ and think of Pascal's Triangle. Each new coefficient is the sum of the two coefficients from the previous exponent combinations which differed from its exponent by $1$. So adding them together produces, e.g. $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$, when you work it out. You end up with a solution to your problem and a visualization of how it got there.
