Proof by induction (binomial theorem)

Question

Let $n\in N$, $k\in Z$, $o\leq k \leq n$. Define $C^{n}_k$ as the coefficient of $x^{n-k}y^k$ in the expansion of $(x+y)^n$

$$(x+y)^n= \sum^{n}_{k=0} C^{n}_k x^{n-k}y^k$$

Use induction to prove that if $k<n$ then $C^{n}_k + C^{n}_{k+1}=C^{n+1}_{k+1}$ hint: $(x+y)^{n+1}=(x+y)^n(x+y)$

Approach

I am not so sure how to use induction here but here is what I think:

$(x+y)^1=x+y=\sum^{1}_{k}x^{1-k}y^{k} = C^1_0 x + C^1_1 y$ so $C^1_0=1$ $C^1_1=1$

left = $C^1_0+C^1_1=2$
$(x+y)^2=x^2+2xy+y^2=\sum^2_{0} C^2_k x^{2-k}y^k= C^{2}_0 x^2+ C^2_1xy+ C^2_2 y^2$ so $C^2_1=2$
Right=$C^2_1$=2
so left=right

at the way end I ended up with something like this

$(x+y)^n(x+y)=C^n_0 x^{n+1}+C^n_n y^{k+1}+ \sum^{n-1}_0 C^n_{k+1} x^{n-k}y^{k+1} + \sum^{n-1}_0 C^n_{k} x^{n-k} y^{k+1}$ As you realize I can apply my inductive hypothesis there, but I don't know how it would take to a degree of n+2

Answer 1

Your inductive step, and in fact your whole inductive hypothesis, is wrong. Don't worry too much about it, induction causes a lot of confusion when you first encounter it. You just have to take it slowly and not jump over too many steps. Always second-guess everything you do, and make sure you have an explanation for every step.

---

Remember, induction is a process you use to prove a statement about all positive integers, i.e. a statement that says "For all $n\in\mathbb N$, the statement $P(n)$ is true".

You prove the statement in two parts:

1. You prove that $P(1)$ is true.
2. You prove that if $P(n)$ is true, then $P(n+1)$ is also true.

So, in your case, you need to ask yourself:

1. What is the statement I want to prove?
2. Can this statement be rewritten into the form $\forall n\in N: P(n)$?
3. If it can, what is $P(n)$?

Please, first answer these questions (preferably either in comments or as an edit to your question), then I can help you further.

---

OK, so you know what $P(n)$ is. Now, you need to do the two steps of proving by induction. First of all, you need to prove $P(1)$. So, these are the questions you need to answer:

1. What is $P(1)$?
2. How can I prove $P(1)$?

When you answer the first question, the second question should be easy to answer, since you know that $(x+y)^1=1\cdot x+1\cdot y$, and you can read out what $C_0^1$ and $C_1^1$ are.

---

Now, the hard part. You need to assume that $P(n)$ is true, and then prove that $P(n+1)$ is true.

To do that, first write down $P(n)$ and $P(n+1)$.

Answer 2

for $n=1$ we have $${{(x+y)}^{\,1}}=\ 1\ =\sum\limits_{i=0}^{1}{\left( \begin{matrix} 1 \\ 0 \\ \end{matrix} \right)}\,{{x}^{1-i}}{{y}^{i}}=\left( \begin{matrix} 1 \\ 0 \\ \end{matrix} \right)\,{{x}^{1}}+\left( \begin{matrix} 1 \\ 1 \\ \end{matrix} \right)\,{{y}^{1}}=x+y$$

for $n=k$ let $$(x+y){{\,}^{k}}=\ \sum\limits_{i=0}^{k}{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}\ {{x}^{k-i}}{{y}^{i}}$$

for $n=k+1$ we show $$\left( x+y \right){{\,}^{k+1}}\,=\ \sum\limits_{i=0}^{k+1}{\left( \begin{matrix} k+1 \\ i \\ \end{matrix} \right)}\ {{x}^{k-i+1}}{{y}^{i}}$$ proof

$$\left( x+y \right){{\,}^{k}}\left( x+y \right)\ =\ \left( x+y \right)\ \sum\limits_{i=0}^{k}{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)\ {{x}^{k-i}}}\ {{y}^{i}}\quad $$ as a result $$\left( x+y \right){{\,}^{k+1}}=\sum\limits_{i=0}^{k}{\,\,\,\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}\ {{x}^{k\,-\,i\,\,+\,1}}{{y}^{i}}\ +\,\sum\limits_{i=0}^{k}{\,\,\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}\ {{x}^{k\,-\,i}}{{y}^{i\,+\,1}}$$

$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, =x\sum\limits_{i=0}^{k}{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}\ {{x}^{k-i}}{{y}^{i}}+y\ \sum\limits_{i=0}^{k}{\left( \begin{matrix} k \\ i \\ \end{matrix} \right)}\ {{x}^{k-i}}{{y}^{i}} $$ By expanding the last equation \begin{align} & {{\left( x+y \right)}^{\,k+1}}\ =\,\left( \begin{matrix} k \\ 0 \\ \end{matrix} \right)\,\,{{x}^{\,k+1}}\,\,+\,\,\left( \begin{matrix} k \\ 1 \\ \end{matrix} \right)\,\,{{x}^{k}}y+\cdots +\,\left( \begin{matrix} k \\ k-1 \\ \end{matrix} \right)\,\,{{x}^{2}}{{y}^{k-1}}+\left( \begin{matrix} k \\ k \\ \end{matrix} \right)\,\,x{{y}^{k}} \\ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \\ \end{align} $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,+\left( \begin{matrix} k \\ 0 \\ \end{matrix} \right)\,\,{{x}^{k}}y+\cdots +\,\left( \begin{matrix} k \\ k-2 \\ \end{matrix} \right)\,{{x}^{2}}{{y}^{k-1}}+\,\left( \begin{matrix} k \\ k-1 \\ \end{matrix} \right)\,\,x{{y}^{k}}+\,\left( \begin{matrix} k \\ k \\ \end{matrix} \right)\,\,{{y}^{k+1}}$$ we know$$\left( \begin{matrix} k \\ i \\ \end{matrix} \right)=\left( \begin{matrix} k-1 \\ i \\ \end{matrix} \right)+\left( \begin{matrix} k-1 \\ i-1 \\ \end{matrix} \right)$$ then $$\,\left( x+y \right){{\,}^{k+1}}\,=\ \sum\limits_{i=0}^{k+1}{\left( \begin{matrix} k+1 \\ i \\ \end{matrix} \right)}\ {{x}^{k-i+1}}{{y}^{i}}$$

Answer 3

Just a complement : Proof using combinatorial argument

Let $X$ a set with $x$ elements, $Y$ set with $y$ elements s.t. $X\cap Y=\emptyset$ and $N$ a set with $n$ element. $$(x+y)^n=\#\{f:N\to X\cup Y\mid f\text{ is a function}\}.$$

An other way to count such a function is the following one. Let $f_k$ a function that through $k$ elements in $X$ and $n-k$ elements in $y$. So, it choose $\binom{n}{k}$ element of $n$, and each such element has $x$ possibilities. Then you take the other $\binom{n-k}{n-k}$ element, and each element has $y$ possibilities. Then, $$\#\{f_k:N\longrightarrow X\cup Y\}=\binom{n}{k}x^k\binom{n-k}{n-k}y^{n-k}=\binom{n}{k}x^ky^{n-k}.$$ Finally $$(x+y)^n=\#\{f:N\to X\cup Y\mid f\text{ is a function}\}=\sum_{k=0}^n\#\{f_k:N\longrightarrow X\cup Y\}$$ $$=\sum_{k=0}^n \binom{n}{k}x^ky^{n-k}$$