WikiSort.ru - Не сортированное

Докажем формулу бинома Ньютона индукцией по n:

База индукции: ${\displaystyle n=0}$

${\displaystyle (a+b)^{0}=1={\binom {0}{0}}a^{0}b^{0}}$

Шаг индукции: Пусть утверждение для ${\displaystyle n}$ верно:

${\displaystyle (a+b)^{n}=\sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k}}$

Тогда надо доказать утверждение для ${\displaystyle n+1}$ :

${\displaystyle (a+b)^{n+1}=\sum _{k=0}^{n+1}{{n+1} \choose k}a^{n+1-k}b^{k}}$

Начнём доказательство:

${\displaystyle (a+b)^{n+1}=(a+b)(a+b)^{n}=(a+b)\sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k}=\sum _{k=0}^{n}{n \choose k}{a^{n-k+1}b^{k}}\quad +\quad \sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k+1}}$

Извлечём из первой суммы слагаемое при ${\displaystyle k=0}$

${\displaystyle \sum _{k=0}^{n}{n \choose k}{a^{n-k+1}b^{k}}=a^{n+1}+\sum _{k=1}^{n}{n \choose k}a^{n-k+1}b^{k}}$

Извлечём из второй суммы слагаемое при ${\displaystyle k=n}$

${\displaystyle \sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k+1}=b^{n+1}+\sum _{k=0}^{n-1}{n \choose k}a^{n-k}b^{k+1}=b^{n+1}+\sum _{k=1}^{n}{n \choose {k-1}}a^{n-k+1}b^{k}}$

Теперь сложим преобразованные суммы:

${\displaystyle a^{n+1}+\sum _{k=1}^{n}{n \choose k}a^{n-k+1}b^{k}\quad +\quad b^{n+1}+\sum _{k=1}^{n}{n \choose {k-1}}a^{n-k+1}b^{k}=a^{n+1}+b^{n+1}+\sum _{k=1}^{n}\left({n \choose k}+{n \choose {k-1}}\right)a^{n-k+1}b^{k}=}$

${\displaystyle =\sum _{k=0}^{0}{n+1 \choose k}a^{n+1-k}b^{k}\quad +\quad \sum _{k=n+1}^{n+1}{n+1 \choose k}a^{n+1-k}b^{k}\quad +\quad \sum _{k=1}^{n}{n+1 \choose k}a^{n+1-k}b^{k}=\sum _{k=0}^{n+1}{{n+1} \choose k}a^{n+1-k}b^{k}}$

Что и требовалось доказать. ■