Общее описание метода математической индукции.

Нередко случается, что нужно доказать утверждение, содержащее натуральный параметр (обозначим его $n$). В таких случаях можно поступить так:

1. Доказать это утверждение для $n=1$ (это называется базой индукции).

2. Доказать, что из верности доказываемого утверждения при одном значении параметра $n=k$ следует его верность при следующем значении параметра $n=k+1$ (что называется шагом индукции).

Это докажет нужное утверждение при всех значениях параметра, и вот каким образом: из верности для $n=1$, доказанной в п.1, следует (в силу шага) верность для $n=2$; а из верности для $n=2$ следует верность для $n=3$, а отсюда для $n=4$ и т.д.

Пример: Демидович №2. Доказать, что для $n\in\mathbb{N}$ \begin{equation} 1^{2}+2^{2}+\dots+n^{2}=\sum_{m=1}^{n}m^{2}=\frac{n\left(n+1\right)\left(2n+1\right)}{6}.\label{dem2} \end{equation} 1. Пусть $n=1$. Тогда сумма слева состоит из одного слагаемого, и действительно равна правой части: \[ 1^{2}=\frac{1\left(1+1\right)\left(2+1\right)}{6}=\frac{1\cdot2\cdot3}{6}=\frac{6}{6}=1. \] 2. Пусть теперь $n=k$, и при нём формула (\ref{dem2}) верна: \begin{equation} 1^{2}+2^{2}+\dots+k^{2}=\frac{k\left(k+1\right)\left(2k+1\right)}{6}.\label{dem2k} \end{equation} Докажем, что отсюда следует верность для $n=k+1$: \begin{equation} 1^{2}+2^{2}+\dots+k^{2}+\left(k+1\right)^{2}\overset{?}{=}\frac{\left(k+1\right)\left(\left(k+1\right)+1\right)\left(2\left(k+1\right)+1\right)}{6}=\frac{\left(k+1\right)\left(k+2\right)\left(2k+3\right)}{6}.\label{dem2k1} \end{equation} Замечу, что формулу, к которой надо прийти при доказательстве шага, обязательно надо выписать (хоть пока мы в ней и не уверены), чтобы знать к чему стремиться. Возьмём верную формулу (\ref{dem2k}), и прибавим к обеим частям её $\left(k+1\right)^{2}$. От этого левая часть сразу станет такой, как в (\ref{dem2k1}), а над правой – подумаем: \[ 1^{2}+2^{2}+\dots+k^{2}+\left(k+1\right)^{2}=\frac{k\left(k+1\right)\left(2k+1\right)}{6}+\left(k+1\right)^{2}=\frac{\left(k+1\right)}{6}\left[k\left(2k+1\right)+6\left(k+1\right)\right]=\frac{\left(k+1\right)}{6}\left(2k^{2}+k+6k+6\right)= \] \[ =\frac{\left(k+1\right)}{6}\left(2k^{2}+7k+6\right). \] Но \[ \frac{\left(k+1\right)\left(k+2\right)\left(2k+3\right)}{6}=\frac{\left(k+1\right)}{6}\left(\left(2k^{2}+3k\right)+\left(4k+6\right)\right)=\frac{\left(k+1\right)}{6}\left(2k^{2}+7k+6\right). \] Таким образом, \[ 1^{2}+2^{2}+\dots+k^{2}+\left(k+1\right)^{2}=\frac{\left(k+1\right)\left(k+2\right)\left(2k+3\right)}{6}, \] что совпадает с (\ref{dem2k1}). Шаг доказан, база доказана, значит, формула (\ref{dem2}) верна при любых натуральных $n$.

Метод математической индукции можно расширить и на целые параметры, минимальное значение которых не равно 1. В таком случае база доказывается для минимального значения, а шаг доказывается так же.

Задание: Демидович, № 1, 3, 4.

Бином Ньютона.

Тем же методом доказывается и формула для разложения натуральных степеней суммы двух слагаемых (известная, как бином Ньютона) \begin{equation} \left(a+b\right)^{n}=\sum_{k=0}^{n}C_{n}^{k}a^{n-k}b^{k}=C_{n}^{0}a^{n}+C_{n}^{1}a^{n-1}b+C_{n}^{1}a^{n-2}b^{2}+\dots+C_{n}^{n}b^{n},\quad C_{n}^{k}=\frac{n!}{k!\left(n-k\right)!}.\label{binom} \end{equation} На всякий случай: $n!$ – это факториал числа $n$, и определяется он так: $n!=1\cdot2\cdot\dots\cdot n$. Считается (почему – станет известно только на 2-м курсе), что $0!=1$. Одно из свойств факториала (довольно очевидных): $n!=n\cdot(n-1)!$.

Сначала нам понадобится одна вспомогательная формула: \[ C_{n-1}^{k-1}+C_{n-1}^{k}=\frac{\left(n-1\right)!}{\left(k-1\right)!\left(\left(n-1\right)-\left(k-1\right)\right)!}+\frac{\left(n-1\right)!}{k!\left(\left(n-1\right)-k\right)!}=\frac{\left(n-1\right)!}{\left(k-1\right)!\left(n-k\right)!}+\frac{\left(n-1\right)!}{k!\left(n-k-1\right)!}= \] \[ =\frac{\left(n-1\right)!k}{k!\left(n-k\right)!}+\frac{\left(n-1\right)!\left(n-k\right)}{k!\left(n-k\right)!}=\frac{\left(n-1\right)!}{k!\left(n-k\right)!}\left[k+\left(n-k\right)\right]=\frac{n!}{k!\left(n-k\right)!}=C_{n}^{k}. \]

1. Пусть $n=1$. $C_{1}^{0}=\frac{1!}{0!\left(1-0\right)!}=\frac{1}{1\cdot1}=1$, $C_{1}^{1}=\frac{1!}{\left(1-0\right)!0!}=1$. В левой части (\ref{binom}) \[ \left(a+b\right)^{1}=a+b. \] Но и в правой части \[ C_{n}^{0}a^{1}+C_{n}^{1}b^{1}=1\cdot a^{1}+1\cdot b^{1}=a+b, \] так что части, действительно, равны

2. Пусть теперь известно, что при $n=m$ \[ \left(a+b\right)^{m}=\sum_{k=0}^{m}C_{m}^{k}a^{m-k}b^{k}. \] Докажем, что отсюда следует, что и при $n=m+1$ \[ \left(a+b\right)^{m+1}\overset{?}{=}\sum_{k=0}^{m+1}C_{m+1}^{k}a^{m+1-k}b^{k}. \] \[ \left(a+b\right)^{m+1}=\left(a+b\right)\sum_{k=0}^{m}C_{m}^{k}a^{m-k}b^{k}=\sum_{k=0}^{m}C_{m}^{k}a^{m-k+1}b^{k}+\sum_{k=0}^{m}C_{m}^{k}a^{m-k}b^{k+1}= \] Произведём переобозначение переменных суммирования: пусть в первой сумме $k=j$, а во второй $k+1=j$ ($k=j-1$) \[ =\sum_{j=0}^{m}C_{m}^{j}a^{m-j+1}b^{j}+\sum_{j=1}^{m+1}C_{m}^{j-1}a^{m-j+1}b^{j}=C_{m}^{0}a^{m-0+1}b^{0}+\sum_{j=1}^{m}C_{m}^{j}a^{m-j+1}b^{j}+\sum_{j=1}^{m}C_{m}^{j-1}a^{m-j+1}b^{j}+C_{m}^{m+1-1}a^{m-m-1+1}b^{m+1}= \] Наконец используем, что $C_{m}^{0}=C_{m+1}^{0}=1$, $C_{m}^{m}=C_{m+1}^{m+1}=1$ и припишем к сумме отсоединённые ранее слагаемые \[ =C_{m}^{0}a^{m+1}+\sum_{j=1}^{m}\left(C_{m}^{j}+C_{m}^{j-1}\right)a^{m-j+1}b^{j}+C_{m}^{m}b^{m+1}=C_{m+1}^{0}a^{m+1}+\sum_{j=1}^{m}C_{m+1}^{j}a^{m-j+1}b^{j}+C_{m+1}^{m+1}b^{m+1}=\sum_{j=0}^{m+1}C_{m+1}^{j}a^{m+1-j}b^{j}, \] что и требовалось доказать.

Задания: Разложить \[ \left(3x-2\right)^{4};\qquad\left(\frac{a}{2}+2\right)^{6} \] Найти слагаемое в разложении, содержащее $x^{2}$: \[ \left(\sqrt{x}+\frac{1}{\sqrt{x}}\right)^{10} \]

Математическая индукция для неравенств.

Математическая индукция применяется и для неравенств.

Пример: Докажем утверждение из №7, но в более строгом варианте. Пусть $x > -1$, $x\neq0$ и $n > 1$. Тогда \begin{equation} \left(1+x\right)^{n} > 1+nx.\label{eq:n7} \end{equation} Вначале проверим это утверждение для минимального натурального $n$, большего единицы: $n=2$. Если $x\neq0$, то $x^{2} > 0$ и \[ \left(1+x\right)^{2}=1+2x+x^{2} > 1+2x, \] и неравенство (\ref{eq:n7}) выполняется. Положим теперь, что при $n=k$ верно \begin{equation} \left(1+x\right)^{k} > 1+kx.\label{eq:k7} \end{equation} Исходя из этого докажем, что \[ \left(1+x\right)^{k+1} > 1+\left(k+1\right)x. \] Так как $x^{2} > 0$, то при натуральных (а значит, и положительных) $k$ и $kx^{2} > 0$. Зная это, умножим обе части считающегося верным неравенства (\ref{eq:k7}) на $\left(1+x\right)$: \[ \left(1+x\right)^{k}\left(1+x\right) > \left(1+kx\right)\left(1+x\right), \] откуда \[ \left(1+x\right)^{k+1} > \left(1+kx\right)\left(1+x\right). \] Но \[ \left(1+kx\right)\left(1+x\right)=1+kx+x+kx^{2}=1+\left(k+1\right)x+kx^{2} > 1+\left(k+1\right)x. \] Итак, \[ \left(1+x\right)^{k+1} > \left(1+kx\right)\left(1+x\right) > 1+\left(k+1\right)x, \] что и требовалось доказать.

Задание: Демидович № 7, 8, 9.