Proof of $(a+b)^{n+1}$

I have to do proof of $(a+b)^n$ and $(a+b)^{n+1}$ with mathematical induction.

I finished the first one $(a+b)^n = a^n + na^{n-1}b+\dots+b^n$.

I however have trouble with the second one, I don't know what to start exactly. Any help/hints?

Solution 1:

Note that $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$, so

$$\begin{align} (a+b)^{n+1}&=(a+b)^n(a+b)\\&=\left(\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k}\right)(a+b)\\ &=\sum_{k=0}^{n}\binom{n}{k}a^{k+1}b^{n-k}+\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k+1}\\ &=a^{n+1}+\sum_{k=1}^{n}\binom{n}{k-1}a^kb^{n-k+1}+\sum_{k=1}^{n}\binom{n}{k}a^kb^{n-k+1}+b^{n+1}\\ &=a^{n+1}+\sum_{k=1}^{n}\left(\binom{n}{k-1}+\binom{n}{k}\right)a^kb^{n-k+1}+b^{n+1}\\ &=a^{n+1}+\sum_{k=1}^{n}\binom{n+1}{k}a^kb^{n-k+1}+b^{n+1}\\&=\sum_{k=0}^{n+1}\binom{n+1}{k}a^kb^{n-k+1}.\end{align}$$

Solution 2:

I think you need to understand the mathematical induction well.

You want to show the binomial theorem $(a+b)^n = \sum_{i = 0}^{n} \binom{n}{i}a^ib^{n-i}$, right?

To do this, You need to assume that this statement is true when $n = N$, then prove for the $n = N+1$ case with your assumption.

Then, if this is true for $n = 1$, then it is true for $n =2$, and so on for $n = 3,4, \cdots$ . So, for every natural number, the statement is true.

So, you should assume that $(a+b)^n = \sum\binom{n}{i}a^ib^{n-i}$, and prove $(a+b)^{n+1} = \sum\binom{n+1}{i}a^ib^{n+1-i}$.

I will show you a little example about induction; Prove $2^n > n$ for every natural number.

First, check the initial case; $2^1 = 2 >1$.

Now, assume that the statement is true when $n=N$, i.e. $2^N > N$. Note that this is not the end of the proof; we did nothing yet. This is just an assumption. With this assumption, we will see what could be happened.

$2^{N+1} = 2^N \times 2 = 2^N + 2^N > 2N \ge N + 1$. (By our assumption)

This is $n = N+1$ case, so we proved the statement. Now the statement is true for $n = 2$, $n=3$, $\cdots$.

Solution 3:

Consider,

$$ e^x e^y = e^{x+y}$$

Expand out both sides as power series:

$$ \sum_i \frac{x^i}{i!} \sum_j \frac{y^j}{j!} = \sum_{k=0}^{\infty} \frac{(x+y)^k}{k!} \tag{1}$$

Consider sum on LHS,

$$ \sum_{ i, j \geq 0}^{\infty}\frac{x^i y^j}{i! j!} $$

Now, consider summing the series as sets of homogenous polynomials that is set the condition, $i+j=k$ this makes our sum:

$$ \sum_{k=0}^{\infty} \left(\sum_{i=0}^k \frac{ x^i y^{k-i} }{i! (k-i)!} \right) \tag{2}$$

Equate RHS of (1) to (2):

$$ \sum_{k=0}^{\infty} \left(\sum_{i=0}^k \frac{ x^i y^{k-i} }{i! (k-i)!} \right) = \sum_{k=0}^{\infty} \frac{(x+y)^k}{k!}$$

Rewrite this sum as:

$$ \sum_{k=0}^{\infty} Q_k = \sum_{k=0}^{\infty} P_k$$

Now notice that $Q_k$ is a homogenous polynomial of degree $k$, and $P_k$ is also a homogenous polynomial of degree $k$, hence these two quantities must be equal Refer

$$ \sum_{i=0}^k \frac{ x^i y^{k-i}}{i!(k-i)!} = \frac{(x+y)^k}{k!}$$

Or rearranging,

$$ \sum_{i=0}^k \binom{k}{i} x^i y^{k-i} = (x+y)^k$$