Примеры по теме "Математическая индукция"

Пример 1. Найти сумму S_n  первых n нечетных чисел:

S_n = 1+ 3 + 5 + ... + (2п- 1).

В таких ситуациях обычно начинают рассматривать частные случаи:

S₁=1;    S₂=1+3=4;   S₃=1+3+5=9;

S₄ = 1 + 3 + 5 + 7= 16;       S₅ = 1 + 3 + 5 + 7 + 9 = 25.

Какой вывод можно сделать на основе этих частных случаев? В данном случае высказать гипотезу несложно:

сумма первых п нечетных чисел равна квадрату их числа, т. е. квадрату числа складываемых нечетных чисел: S_n = п².

Пример 2. Пусть требуется найти

S_n = 1 • 3 + 3 • 5 + 5 • 7 + ... + (2n - 1)(2n + 1)

для каждого натурального п.

Рассмотрим частные случаи: S₁ = 3, S₂ = 18.

Предположим, что

S_n= 1 • 3+3 • 5+5 • 7 + ... + (2n - 1)(2n + 1) = 3n(2n - 1).

Попробуем доказать справедливость этого утверждения методом математической индукции.

1. Базис индукции:

S₁=1 • 3 = 3 • 1 ·(2 • 1-1) — равенство верно.

2. Индуктивное предположение: Пусть формула

S_k= 1 • 3 + 3 • 5 + 5 • 7 + ... + (2k - 1)(2k + 1) = 3k(2k - 1)

верна для некоторого произвольного k> 1.

3. Индуктивный переход. Надо доказать справедливость равенства

S_k+1= 1 • 3+3 • 5+5 • 7 + ... + (2k + 1)(2k + 3) = 3(k + 1)(2k + 1).

Очевидно, что S_k+1 = S_k + (2k + 1)(2k + 3). Так как S_k = 3k (2k - 1), то

S_k+1=3k(2k –1) + (2k+1)(2k + 3) = 10k² + 5k + 3,

но нам нужно было получить

S_k+1 = 3(k + 1)(2k + 1) = 6k² + 9k + 3.

       Так как у нас получился иной результат, то высказанное предположение неверно; на самом деле справедлива формула

Пример 3. Доказать, что при любых натуральных п число 7ⁿ + 12п+ 17 делится на 18.

    Доказательство.

    1. При n = 1 число 7¹ + 12 • 1 + 17 = 36 кратно 18.

 2.  Предположим,     что    для    некоторого    натурального   числа  k ≥ 1     число

7^k + 12k + 17 делится на 18.

3. Рассмотрим число 7^k+1 + 12(k + 1) + 17 и докажем, что оно кратно 18.

Выделим из выражения 7^k+1 + 12(k + 1) + 17 число 7^k + 12k +17, которое на основании предположения индукции делится на 18. Получим: 7^k+1 + 12(k + 1) + +17 = 7 • (7^k + 12k + 17) - 6 • 12k - 90 = 7 • (7^k + 12k + 17) - (6 • 12k + 90).

           Мы видим, что при любом натуральном k число 6 • 12k + 90 = 18(4k + 5)

кратно 18. Итак, мы представили число 7^k+1+12(k + 1) + 17 в виде разности двух чисел, каждое из которых делится на 18. Следовательно, и

само число 7^k+1 + 12(k + 1) + 17 кратно 18.

Пример 4. Доказать, что при всех натуральных n > 4 выполняется неравенство 2ⁿ >n² .

Решение.

1.                                                                 Базис индукции. При n = 5 имеем неравенство 2⁵ > 5², которое выполняется

    (32 > 25), значит, утверждение А(5) верно.

2. Предположение индукции. Пусть при некотором произвольном натуральном числе n = k ≥ 5 справедливо неравенство 2^k > k².

3. Индуктивный переход. Докажем справедливость неравенства 

2^k+1 > (k + 1)² . Имеем 2^k+1 = 2 • 2^k , но по предположению индукции 2^k > k² . Умножив последнее неравенство на 2, получим 2 • 2^k > 2k² .

Запишем последнее неравенство в виде

2^k+1>(k+1)²+(2k²-(k+1)²).               (4)

Если мы докажем, что при любом натуральном k > 5 выражение 2k² - (k + 1)² положительно, то из неравенства (4) получим

2^k+1> (k + 1)² + (2k² - (k +1)²) > (k +1)²,

т. е. требуемое неравенство.

Рассмотрим разность

2k²-(k +1)² = k² – 2k-1 = (k - 1)² - 2.

Но при любом k > 5 имеем (k - 1)² > 2. Следовательно, (k - 1)² - 2 > 0 при всех значениях k > 5.

Итак, согласно принципу математической индукции данное неравенство справедливо при всех натуральных n > 4.

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

              неравенство 4ⁿ > 7п - 5.

Доказательство.

В данном случае проверим наше неравенство для п = 1 и п = 2.

1. При п = 1 неравенство 4¹ > 7 • 1-5  верно. При п = 2 имеем

4² > 7 • 2-5 также верное неравенство.

2. Предположим, что для некоторого натурального числа k≥2 выполняется неравенство 4^k > 7k - 5.

3. Докажем, что справедливо неравенство 4^k+1 > 7(k + 1) - 5. Умножив обе части неравенства из пункта 2 на 4, мы получим верное неравенство

4 • 4^k > 4(7k - 5) <=> 4^k+1 > (7(k +1) - 5) + 21(k - 1) - 1.      (1)

 Но при любом k≥2 число

21(k - 1) – 1= 21(k - 2) + 20 > 0.                  (2)

Следовательно, справедливо неравенство

7(k+1)-5+21(k- 1) - 1 > 7(k + 1)-5              (3)

Из неравенств (1) и (3) следует неравенство

4^k+1>7(k+ 1)-5.

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

Замечание. В данном случае базис индукции — пункт 1 — содержит доказательство данного утверждения для первых двух натуральных чисел n = 1 и n = 2. Это связано с тем, что неравенство (2) не выполняется при k = 1, но справедливо при каждом натуральном k > 1. Поэтому, доказав данное неравенство для n = 1и n = 2, в дальнейшем рассматривались числа k≥2.

Пример 6. Доказать, что если для n положительных чисел а_1, а₂,...,а_n (n> 1) выполнено условие a₁а₂...а_n=1, то

        a₁ + a₂ + ... + a_n ≥ n                               (5)

Решение. 1. Базис индукции. Докажем справедливость утверждения при натуральном n = 2. Пусть a₁ = а > 0, а₂ = b > 0, аb = 1. Тогда

b=1/a . Рассмотрим разность а + b - 2:

a+b-2=a+

Таким образом, а + b - 2 ≥ 0, откуда а + b ≥ 2, т.е. утверждение А(1) верно.                             

2.                                                                 Предположение индукции. Пусть данное утверждение справедливо для всех

n=k>2, т. е. для k положительных чисел а_1,а₂,...,а_k таких, что а₁а₂..а_k = 1, выполняется неравенство а₁ + a₂ + ... + а_k≥k.

3. Индуктивный переход. Докажем, что если произведение k + 1 положительных чисел равно 1, т. е. а₁а₂...а_k+1= 1, то их сумма не меньше количества слагаемых:

а₁, +а₂ + ... +а_k+1≥ k + 1.                     (6)

Отметим, что если все данные числа равны между собой, то каждое из них равно 1 и неравенство (6), очевидно, выполняется. Предположим, что хотя бы одно из заданных положительных чисел меньше 1, например, 0 < a_k+1 < 1. Тогда среди оставшихся найдется такое положительное число, которое больше единицы. Пусть а_k > 1 (если какие-то другие два числа обладают указанными свойствами, то мы просто их перенумеруем).

Рассмотрим произведение k чисел: а_1,a₂,...а_k-1(a_ka_k+1) = 1. По условию все эти числа положительны:

a₁>0,  а₂>0, .... а_k-1>0, а_ka_k+1>0,

значит, по предположению индукции имеем

а₁+а₂+...+а_k-1+(а_kа_k+1)≥k.               (7)

Чтобы доказать неравенство (6), перепишем неравенство (7) следующим образом:

a₁+а₂+...+а_k-1+а_k+а_k+1≥k+1+(а_k+а_k+1-а_ka_k+1-1).               (8)

Для доказательства неравенства (6) осталось доказать, что

a_k+a_k+1 –a_ka_k+1>0

Левую часть последнего неравенства можно записать так:

a_k+a_k+1-a_ka_k+1-1= (a_k-1)+(a_k+1-a_ka_k+1)=

=(a_k-1)+a_k+1(1-a_k)=(a_k-1)-a_k+1(a_k-1)=(a_k-1)(1-a_k+1).

Но по условию а_k> 1 и а_k+1 < 1. Поэтому

a_k+a_k+1-а_ka_k+1-1⁼(a_k-1)(1-a_k+1)>0          (9)

Тогда неравенство (8) с учетом (9) примет вид

a₁+а₂+...+a_k+1+a_k+a_k+1≥k+1+ (а_k + а_k+1- а_kа_k+1- 1) > k + 1.

Итак, неравенство(6)доказано.