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

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

Ответы

Задачи для самостоятельного решения

1. Заданы предикаты

Р(x,y,z):

Q(x,y,z):

R(x,y,z):

S(a,b,c): a нравится b больше, чем c

Запишите следующие высказывания: а) Р(1, 2, -5); б) Q(7,10); в) R(0,1); г) S(Миша, Марина, Таня).

2. Используя P,Q,R,S из упражнения 1, запишите высказывания:

а) ; б) ; в) ; г) ; д) .

3. Пусть Q(x,y,z): , предметная область для x, y, z– множество целых чисел. Что можно сказать об истинности ?

4. Пусть P(x,y,z): . Какой должна быть предметная область, чтобы следующее высказывание было истинным:

1. а) Р(1,2,-5): ; б) ; г) Мише Марина нравится больше, чем Таня. 2. а) существуют x и y такие, что ; в) для каждого y существует x такое, что ; г) Мише нравится Марина больше, чем кто-либо. 3. Ложно, например, Q(1,2,3) – ложно. 4. Множество положительных действительных чисел.

(А1) Пусть P(n) – такое утверждение, что

1) P(1) истинно;

2) для каждого к, если P(k) истинно, то P(k+1) истинно

Тогда P(n) истинно для любого целого положительного числа n.

В символической записи:

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

1+2+3+…+ n=

Пусть S_n – утверждение «1+2+3+…+ n= ». Проверим, что S_n истинно для n= 1.

1) S₁ =1= - верно;

2) Предположим, что для любого к утверждение

S_{к =}1+2+3+…+к = - верно.

Требуется доказать, что S_{к +1}=1+2+3+…+ k + k +1= – верно. В самом деле, S_{к +1}=(1+2+3+…+ k)+ k +1= S_к +(k+1)= .

Итак, получили, что S_{к +1}истинно. Следовательно, по индукции, S_n истинно для всех натуральных n.

Пример 2. Требуется показать, что для любого положительного целого числа n, число n³- n делится на 3.

Пусть S_n – утверждение «n³ - n делится на 3». Покажем, что S_n истинно для n= 1.

1) S₁ =1³-1=0, поэтому n³ - n при n =1делится на 3, так как 0= ,.

Таким образом, S₁ истинно.

2) Допустим, что S_k истинно, т.е. k³-k делится на 3, поэтому k³-k=3m для некоторого положительного целого m. Требуется доказать, что S_{к +1} –истинно, т.е. (k+ 1 )³ -(k +1) делится на 3, т.е. существует такое натуральное w, что (k+ 1 )³ -(k +1)=3w.

Преобразуем

(k+ 1 )³ -(k +1)=(k³ +3 k² +3 k +1)-(k +1)=(k³ - k)+(3 k² +3 k)=3 m +3(k² + k)=3w, где w= m +(k² + k). Таким образом, (k+ 1 )³ -(k +1) делится на 3, и следовательно, S_{к +1}истинно. Поэтому, по индукции, S_n истинно для всех натуральных n.

(А2) ( Второй принцип индукции ). Пусть P(n) – утверждение. Если

а) Р(1) истинно, и

б) для произвольного k из истинности P(m) для всех m<k следует истинность P(k),

то P(n) истинно для всех положительных целых чисел n.

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

Теорема (принцип индукции для целых чисел). Пусть P(n) - высказывание, обладающее свойствами

а) P(j) истинно и

б) для произвольного , если P(k) истинно, то P(k+1) истинно.

Тогда P(n) истинно для каждого .

Пример3. Доказать, что для любого целого числа имеет место неравенство

Решение. Согласно обозначениям, введенным для принципа индукции для целых чисел, имеем j=4, P(n) – утверждение «».

1) При n=4 имеем 4!=24 и 2⁴=16, так что 4!>2⁴.

2) Предположим, что k!>2^k. Нужно доказать, что (k+1)!>2^k+1.

Заметим, что (k +1)!= k!(k +1); 2^k+1=2^k2, т.е нужно доказать, что k!(k +1)>2^k2. Покажем, что k +1>2. Так как , то k >2, следовательно, (k +1) k!>2·2^k и (k +1)!>2^k+1.. Таким образом, n!>2ⁿ для каждого .

Дата добавления: 2014-12-27