Метод математической индукции. Допустим, необходимо доказать справедливость бесконечной последовательности утверждений Р(n), зависящих от натуральной переменной n

Допустим, необходимо доказать справедливость бесконечной последовательности утверждений Р(n), зависящих от натуральной переменной n. Метод математической индукции — один из способов доказательства. Он заключается в следующем.

1. Вначале доказывают справедливость Р(n) при n=1 (базис индукции).

2. Затем доказывают, что из истинности Р(k) для любого натурального числа k следует истинность и Р(k+1) (индуктивный переход).

Если оба пункта доказаны, то утверждение Р(n) истинно для всех натуральных чисел. В тех случаях, когда доказывается справедливость Р(n) для всех n³ n₀ >1, базис индукции доказывают при n = n₀ .

Пример 1. Докажем методом математической индукции равенство 1+3+5+…+(2n-1)=n².

Решение.

Базис индукции. n=1: 1=1 — равенство выполняется.

Индуктивный переход. Покажем, что из справедливости равенства для любого натурального числа k следует его истинность для (k+1) (индуктивный переход).

1 + 3 + 5 +…+ (2k–1) + (2(k+1) – 1) = k² + (2(k+1) – 1) = k² + 2k + 1 = (k+1)².

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

Пример 2. Докажем методом математической индукции неравенство log_n 2 > 1/ n при n >1.

Решение. Для упрощения доказательства перейдем к следующему равносильному неравенству: 2ⁿ>n. Его получим, умножая обе части на n и возводя n в степени, стоящие в левой и правой частях.

Базис индукции. n=2: 4>2— неравенство выполняется.

Индуктивный переход. Покажем, что из 2^k > k для любого натурального числа k следует: 2^(k+1)> k+1.

2^(k+1) = 2× 2^k > 2× k ³ ((k +1)/k)× k = k +1.

Справедливость переходов следует из индуктивного допущения 2^k>k и неравенства 2 ³ ((k+1)/k), верного для всех натуральных k (так как при k ³ 1выполняется: 2 k ³ k+1).

По теореме получим, что рассмотренное неравенство справедливо для всех натуральных чисел, больших 1, что и требовалось доказать.

Пример 3. Докажем методом математической индукции, что выражение 1+3^2n-1при всех натуральных n делится нацело (без остатка) на4.

Решение.

Базис индукции. n=1:1+3^2-1= 4 — делится нацело на4.

Индуктивный переход. Покажем, что если 1+3^2k–1для любого натурального числа k делится нацело на 4, то и
1+3^2(k+1)–1 делится нацело на 4 .

1 + 3^{2(k+1) –1}= 1 + 3^{2(k+1) -1}– (1 + 3^2k–1) + 1 + 3^2k–1 = (3^2(k+1)–1 – 3^2k–1 ) + 1 + 3^2k–1 = 3^2k-1× (3² – 1) +1 + 3^2k–1 = 3^2k–1× 8 +1 + 3^2k–1.

Число 1+3^2(k+1)–1представлено в виде суммы двух слагаемых. Первое делится на 4 нацело по индуктивному допущению, второе содержит множитель 8. Следовательно, сумма также делится на 4. Индуктивный переход доказан.

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

ЗАДАЧИ

Доказать по методу математической индукции справедливость для натуральных n следующих соотношений:

1)1² + 2² +…+ n²= n(n+1)(2n+1)/6,

2) 1³+ 2³ +…+ n ³= (1+ 2 +…+ n)²,

3) 7^2n–1+ 6 ^2n–1+ 1кратно 14,

4) 2^2n–1+ 3^2n–1 + 1кратно 6,

5) 2⁵ⁿ – 5²ⁿ кратно 7,

6) 1+ q +…+ qⁿ = (1–qⁿ⁺¹)/(1–q)при q ¹ 1.