Метод математической индукции

п.1. Принцип математической индукции

Рассмотрим бесконечную последовательность утверждений, которую можно отобразить на множество натуральных чисел, т.е., попросту, пронумеровать:
P₁, P₂, ... , P_n , ...

Принцип математической индукции используется для доказательства различных формул.

Например:
Докажем, что сумма первых n натуральных чисел равна \(\mathrm{S_n=1+2+...+n=\frac{n(n+1)}{2}}\)
1) Для базы индукции \(\mathrm{n=1,\ \ S_1=\frac{1\cdot 2}{2}=1}\) – верно
2) Допустим что при некотором \(\mathrm{n\ \ S_n=\frac{n(n+1)}{2}.}\) Найдём S_n+1: \begin{gather*} \mathrm{ S_{n+1}=(1+2+...+n)+n+1=S_n+n+1=\frac{n(n+1)}{2}+(n+1)= }\\ \mathrm{ =\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2} } \end{gather*} т.е. для S_n+1 формула также справедлива. Индуктивный переход выполняется. Следовательно, по принципу математической индукции \(\mathrm{S_n=\frac{n(n+1)}{2},\ \forall n\in \mathbb{N}}\).
Что и требовалось доказать.

п.2. Примеры

Пример 1. Докажите, что сума кубов первых n натуральных чисел равна \(\mathrm{S_n=\frac{n^2(n+1)^2}{4}}\)
1) Для базы индукции \(\mathrm{n=1,\ \ S_1=\frac{1^2(1+1)^2}{4}=1}\) – верно
2) Допустим, что при некотором \(\mathrm{n,\ \ S_n=\frac{n^2(n+1)^2}{4}}\). Найдём S_n+1: \begin{gather*} \mathrm{ S_{n+1}=\underbrace{1^3+2^3+3^3+...+n^3}_{S_n}+(n+1)^3=S_n+(n+1)^3= }\\ \mathrm{ =\frac{n^2(n+1)^2}{4}+(n+1)(n+1)^2=\frac{n^2(n+1)^2+4(n+1)(n+1)^2}{4} }\\ \mathrm{ =\frac{(n+1)^2(n^2+4(n+1))}{4}=\frac{(n+1)^2(n^2+4n+4)}{4}=\frac{(n+1)^2(n+2)^2}{4} } \end{gather*} т.е. для S_n+1 формула также справедлива. Индуктивный переход выполняется. Следовательно, по принципу математической индукции сумма кубов \(\mathrm{S_n=\frac{n^2(n+1)^2}{4},\ \forall n\in \mathbb{N}}\). Что и требовалось доказать.

Заметим, что согласно доказанной формуле сумма кубов является точным квадратом суммы первых степеней: $$ \mathrm{ 1^3+2^3+3^3+...+n^3=\left(\frac{n(n+1)}{2}\right)^2=(1+2+3+...+n)^2 } $$

Пример 2. Докажите формулу Архимеда $$ \mathrm{1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}} $$
1) Для базы индукции \(\mathrm{n=1,\ \ S_1=\frac{1(1+1)(2+1)}{6}=1}\) – верно
2) Допустим, что при некотором \(\mathrm{n,\ \ S_n=\frac{n(n+1)(2n+1)}{6}}\). Найдём S_n+1: \begin{gather*} \mathrm{ S_{n+1}=\underbrace{1^2+2^2+3^2+...+n^2}_{S_n}+(n+1)^2=S_n+(n+1)^2= }\\ \mathrm{ =\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\frac{n(n+1)(2n+1)+6(n+1)^2}{6} }\\ \mathrm{ =\frac{(n+1)\left(n(2n+1)+6(n+1)\right)}{6}=\frac{(n+1)(2n^2+7n+6)}{6}= }\\ \mathrm{ =\frac{(n+1)(n+2)(2n+3)}{6}=\frac{(n+1)\left((n+1)+1\right)(2(n+1)+1)}{6} } \end{gather*} т.е. для S_n+1 формула также справедлива. Индуктивный переход выполняется. Следовательно, по принципу математической индукции сумма квадратов \(\mathrm{S_n=\frac{n(n+1)(2n+1)}{6},\ \ \forall n\in\mathbb{N}}\). Что и требовалось доказать.

Пример 3. Докажите, что любой член последовательности a_n = 15ⁿ + 6 делится на 7.
1) Для базы индукции n=1, a₁ = 15 + 6 = 21 – делится на 7, верно
2) Допустим, что при некотором \(\mathrm{n,\ \ a_n=15^n+6 \text{ делится на 7, т.е. }\ \frac{a^n}{7}=k,\ \ k\in\mathbb{N}}\). Рассмотрим дробь \(\mathrm{\frac{a_{n+1}}{7}}\): \begin{gather*} \mathrm{ \frac{a_{n+1}}{7}=\frac{15^{n+1}+6}{7}=\frac{15\cdot 15^n+6}{7}=\frac{(14+1)\cdot 15^n+6}{7}= }\\ \mathrm{ =\frac{14\cdot 15^n+\overbrace{(15^n+6)}^{=a_n}}{7}=\frac{14\cdot 15^n}{7}+\frac{a_n}{7}=2\cdot 15^n+k }\end{gather*} Получаем натуральное число. Значит, a_n+1 также делится на 7. Индуктивный переход выполняется.
Следовательно, по принципу математической индукции a_n = 15ⁿ + 6 делится на 7 при любом натуральном \(\mathrm{n\in\mathbb{N}}\). Что и требовалось доказать.

Пример 4. Докажите, что любой член последовательности a_n = 7ⁿ + 12n делится на 18 с остатком 1.
1) Для базы индукции n=1, a₁ = 7¹ + 12 · 1 = 19 – делится на 18 с остатком 1, верно
2) Допустим, что при некотором $a_n=7^n+12n$ делится на 18 с остатком 1, т.е. $\frac{a_n-1}{18}=k$, $k \in \mathbb {N}$ Рассмотрим дробь \(\mathrm{\frac{a_{n+1}-1}{18}}\): \begin{gather*} \mathrm{ \frac{a_{n+1}-1}{18}=\frac{7^{n+1}+12(n+1)-1}{18}=\frac{7\cdot 7^n+12n-1+12}{18}= }\\ \mathrm{ =\frac{7^n + 12n-1}{18}+\frac{6\cdot 7^n+12}{18}=k+\frac{7^n+2}{3} }\end{gather*} Решаем подзадачу. Докажем, что \(\mathrm{b_n=\frac{7^n+2}{3}}\) всегда является натуральным числом.
1) Для базы индукции n=1, \(\mathrm{b_1=\frac{7+2}{3}=3}\) – верно
2) Допустим, что при некотором \(\mathrm{n,\ \ b_n=\frac{7^n+2}{3}=m \in\mathbb{N}}\). Рассмотрим \(\mathrm{b_{n+1}}\): \begin{gather*} \mathrm{ b_{n+1}=\frac{7^{n+1}+2}{3}=\frac{7\cdot 7^n+2}{3}=\frac{7^n+2}{3}+\frac{6\cdot 7^n}{3}=m+2\cdot7^n }\end{gather*} Получили натуральное число. Индуктивный переход для подзадачи выполняется.
Значит, \(\mathrm{b_n=\frac{7^n+2}{3}}\). всегда является натуральным числом.

Возвращаемся к основной задаче: \(\mathrm{\frac{a_{n+1}-1}{18}=k+\frac{7^n+2}{3}=k+m\in\mathbb{N}}\).
Значит, a_n+1 делится на 18 с остатком 1. Индуктивный переход для основной задачи выполняется.
Следовательно, по принципу математической индукции a_n = 7ⁿ + 12n делится на 18 с остатком 1 при любом натуральном \(\mathrm{n\in\mathbb{N}}\). Что и требовалось доказать.