Proving $(x+y)^n = \sum\limits_{k=0}^n \binom{n}{k} x^k y^{n-k}$

Question

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!

Answer 1

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?

Answer 2

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.

Answer 3

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.

Answer 4

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$$