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! 
 A: Hint: $$\begin{align}
\sum_{k=0}^n &\binom n  k \bigg[ x^{k+1} y^{n-k} + x^k y^{n-k+1} \bigg]\\
&=\color{red}{\sum_{k  = 0}^n {n \choose k} x^{k+1}y^{n-k}} + \color{#00A000}{\sum_{k  = 0}^n {n \choose k} x^{k} y^{n-k+1}}\\
&=\color{red}{{n \choose n} x^{n+1} + \sum_{k  = 0}^{n-1} {n \choose k} x^{k+1} y^{n-k}} + \color{#00A000}{{n \choose 0} y^{n+1} + \sum_{k  = 1}^{n} {n \choose k} x^{k} y^{n-k+1}}\\
&=x^{n+1} + y^{n+1} + \color{royalblue}{\sum_{k  = 0}^{n-1} {n \choose k} x^{k+1} y^{n-k}} + \sum_{k  = 1}^{n} {n \choose k} x^{k} y^{n-k+1}\\
&={n+1 \choose 0} x^{n+1} + {n+1 \choose n+1} y^{n+1} + \color{royalblue}{\sum_{k  = 1}^n {n \choose k-1} x^{k} y^{n-k+1}} + \sum_{k  = 1}^n {n \choose k} x^{k} y^{n-k+1}.\\
\end{align}$$
Can you continue?
A: By induction, illustrating the case $n=3\to n=4$, which easily generalizes:
$$(x+y)\left(\binom33x^3y^0+ \binom32x^2y^1+ \binom31x^1y^2+ \binom30x^0y^3\right)\\=$$
$$\begin{align}\binom33x^4y^0+&\binom32x^3y^1+ \binom31x^2y^2+ \binom30x^1y^3+\\
&\binom33x^3y^1+ \binom32x^2y^2+ \binom31x^1y^3+ \binom30x^0y^4\end{align}\\=$$
$$\binom44x^4y^0+ \binom43x^3y^1+ \binom42x^2y^2+ \binom41x^1y^3+ \binom40x^0y^4\\$$
$$1\ 3\ 3\ 1-\\-1\ 3\ 3\ 1\\1\ 4\ 6\ 4\ 1$$
The base case is just
$$\binom00x^0y^0$$
$$1$$
A: It is much easier if you de-homogeneise the formula, i.e. it's easier to prove:
$$(1+t)^n=\sum_{k=0}^n\binom nk t^k\qquad (\text{setting}\enspace t=\frac yx)$$
Indeed, suppose this formula is true for some $n$, and let's calculate $(1+t)^{n+1}$:
\begin{align*}(1+t)^{n+1}&=(1+t)\biggl(\sum_{k=0}^n\binom nk t^k\biggr)=\sum_{k=0}^n\binom nk t^k+\sum_{k=0}^n\binom nk t^{k+1}\\
&=\sum_{k=0}^n\binom nk t^k+\sum_{k=1}^{n+1}\binom n{k-1} t^{k}\\
&=\binom{n}{0}+\sum_{k=1}^n\binom nk t^k+\sum_{k=1}^n\binom n{k-1} t^k+\binom{n}{n}t^{n+1}\\
&=\binom{n+1}{0}+\sum_{k=1}^n\biggl[\binom nk +\binom n{k-1}\biggr] t^k+\binom{n+1}{n+1}t^{n+1}\\
&=\binom{n+1}{0}+\sum_{k=1}^n\binom {n+1}k t^k+\binom{n+1}{n+1}t^{n+1}.
\end{align*}
Note:
Actually what is proved is this:  denote $c(n,k)$ the coefficient of $t^k$ when developing $(1+t)^n$. These coefficients satisfy the same relations as the $\dbinom nk$s:
$$c(n,0)=c(n,n)=1,\quad c(n+1,k)=c(n,k)+c(n,k-1)\quad\text{for}\enspace 1\le k\le n.$$  Hence by a theorem on recursive functions, they are equal.
A: 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.
