Материалы сайта
Это интересно
Метод математической индукции
По своему первоначальному смыслу слово “индукция” применяется к рассуждениям, при помощи которых получают общие выводы, опи-раясь на ряд частных утверждений. Простейшим методом рассуждений такого рода является пол-ная индукция. Вот пример подобного рассужде-ния. Пусть требуется установить, что каждое натуральное чётное число n в пределах 4< n < 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения: 4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5; 14=7+7; 16=11+5; 18=13+5; 20=13+7. Эти девять равенств показывают, что каждое из интересующих нас чисел действительно пред- ставляется в виде суммы двух простых слагаемых. Таким образом, полная индукция заключает- ся в том, что общее утверждение доказывается по отдельности в каждом из конечного числа возмож- ных случаев. Иногда общий результат удаётся предугадать после рассмотрения не всех, а достаточно большо- го числа частных случаев (так называемая непол- ная индукция). Результат, полученный неполной индукцией, остается, однако, лишь гипотезой, пока он не до- казан точным математическим рассуждением, охватывающим все частные случаи. Иными сло- вами, неполная индукция в математике не счита- ется законным методом строгого доказательства, но является мощным методом открытия новых ис-тин. Пусть, например, требуется найти сумму пер- вых n последовательных нечётных чисел. Рас- смотрим частные случаи: 1=1=12 1+3=4=22 1+3+5=9=32 1+3+5+7=16=42 1+3+5+7+9=25=52 После рассмотрения этих нескольких частных случаев напрашивается следующий общий вывод: 1+3+5+…+(2n-1)=n2 т.е. сумма n первых последовательных нечётных чисел равна n2 Разумеется, сделанное наблюдение ещё не мо- жет служить доказательством справедливости при- ведённой формулы. Полная индукция имеет в математике лишь ог- раниченное применение. Многие интересные мате- матические утверждения охватывают бесконечное число частных случаев, а провести проверку для бесконечного числа случаев мы не в состоянии. Неполная же индукция часто приводит к ошибоч- ным результатам. Во многих случаях выход из такого рода за- труднений заключается в обращении к особому ме- тоду рассуждений, называемому методом матема- тической индукции. Он заключается в следующем. Пусть нужно доказать справедливость некото- рого утверждения для любого натурального числа n (например нужно доказать, что сумма первых n нечётных чисел равна n2). Непосредственная про-верка этого утверждения для каждого значения n невозможна, поскольку множество натуральных чисел бесконечно. Чтобы доказать это утвержде-ние, проверяют сначала его справедливость для n=1. Затем доказывают, что при любом натураль-ном значении k из справедливости рассматрива-емого утверждения при n=k вытекает его справед-ливость и при n=k+1. Тогда утверждение считается доказанным для всех n. В самом деле, утверждение справедливо при n=1. Но тогда оно справедливо и для следую-щего числа n=1+1=2. Из справедливости утвержде-ния для n=2 вытекает его справедливость для n=2+ +1=3. Отсюда следует справедливость утвержде-ния для n=4 и т.д. Ясно, что, в конце концов, мы дойдём до любого натурального числа n. Значит, утверждение верно для любого n. Обобщая сказанное, сформулируем следую-щий общий принцип. Принцип математической индукции. Если предложение А(n), зависящее от натураль-ного числа n, истинно для n=1 и из того, что оно истинно для n=k (где k-любое натуральное число), следует, что оно истинно и для следующего числа n=k+1, то предположение А(n) истинно для любо-го натурального числа n. В ряде случаев бывает нужно доказать спра-ведливость некоторого утверждения не для всех натуральных чисел, а лишь для n>p, где p-фикси- рованное натуральное число. В этом случае прин-цип математической индукции формулируется сле-дующим образом. Если предложение А(n) истинно при n=p и если А(k)(А(k+1) для любого k>p, то предложе-ние А(n) истинно для любого n>p. Доказательство по методу математической ин-дукции проводиться следующим образом. Сначала доказываемое утверждение проверяется для n=1, т.е. устанавливается истинность высказывания А(1). Эту часть доказательства называют базисом индукции. Затем следует часть доказательства, на-зываемая индукционным шагом. В этой части до-казывают справедливость утверждения для n=k+1 в предположении справедливости утверждения для n=k (предположение индукции), т.е. доказывают, что А(k)(A(k+1). ПРИМЕР 1 Доказать, что 1+3+5+…+(2n-1)=n2. Решение: 1) Имеем n=1=12. Следовательно, утверждение верно при n=1, т.е. А(1) истинно. 2) Докажем, что А(k)(A(k+1). Пусть k-любое натуральное число и пусть утверж-дение справедливо для n=k, т.е. 1+3+5+…+(2k-1)=k2. Докажем, что тогда утверждение справедливо и для следующего натурального числа n=k+1, т.е. что 1+3+5+…+(2k+1)=(k+1)2. В самом деле, 1+3+5+…+(2k-1)+(2k+1)=k2+2k+1=(k+1)2. Итак, А(k)(А(k+1). На основании принципа математической индукции заключаем, что предпо-ложение А(n) истинно для любого n(N. ПРИМЕР 2 Доказать, что 1+х+х2+х3+…+хn=(хn+1-1)/(х-1), где х(1 Решение: 1) При n=1 получаем 1+х=(х2-1)/(х-1)=(х-1)(х+1)/(х-1)=х+1 следовательно, при n=1 формула верна; А(1) ис-тинно. 2) Пусть k-любое натуральное число и пусть формула верна при n=k, т.е. 1+х+х2+х3+…+хk=(хk+1-1)/(х-1). Докажем, что тогда выполняется равенство 1+х+х2+х3+…+хk+xk+1=(xk+2-1)/(х-1). В самом деле 1+х+х2+x3+…+хk+xk+1=(1+x+x2+x3+…+xk)+xk+1= =(xk+1-1)/(x-1)+xk+1=(xk+2-1)/(x-1). Итак, А(k)(A(k+1). На основании принципа математической индукции заключаем, что форму-ла верна для любого натурального числа n. ПРИМЕР 3 Доказать, что число диагоналей выпуклого n-угольника равно n(n-3)/2. Решение: 1) При n=3 утверждение спра- А3 ведливо, ибо в треугольнике ?3=3(3-3)/2=0 диагоналей; А2 А(3) истинно. 2) Предположим, что во всяком выпуклом k-угольнике имеет- А1 ся ?k=k(k-3)/2 диагоналей. Аk Докажем, что тогда в выпуклом Аk+1 (k+1)-угольнике число диаго- налей ?k+1=(k+1)(k-2)/2. Пусть А1А2А3…AkAk+1-выпуклый (k+1)-уголь-ник. Проведём в нём диагональ A1Ak. Чтобы под-считать общее число диагоналей этого (k+1)-уголь- ника нужно подсчитать число диагоналей в k-угольнике A1A2…Ak, прибавить к полученному числу k-2, т.е. число диагоналей (k+1)-угольника, исходящих из вершины Аk+1, и, кроме того, следует учесть диагональ А1Аk. Таким образом, ?k+1=?k+(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2. Итак, А(k)(A(k+1). Вследствие принципа математической индукции утверждение верно для любого выпуклого n-угольника. ПРИМЕР 4 Доказать, что при любом n справедливо утвер-ждение: 12+22+32+…+n2=n(n+1)(2n+1)/6. Решение: 1) Пусть n=1, тогда Х1=12=1(1+1)(2+1)/6=1. Значит, при n=1 утверждение верно. 2) Предположим, что n=k Хk=k2=k(k+1)(2k+1)/6. 3) Рассмотрим данное утвержде-ние при n=k+1 Xk+1=(k+1)(k+2)(2k+3)/6. Xk+1=12+22+32+…+k2+(k+1)2=k(k+1)(2k+1)/6+ +(k+1)2=(k(k+1)(2k+1)+6(k+1)2)/6=(k+1)(k(2k+1)+ +6(k+1))/6=(k+1)(2k2+7k+6)/6=(k+1)(2(k+3/2)(k+ +2))/6=(k+1)(k+2)(2k+3)/6. Мы доказали справедливость равенства и при n=k+1, следовательно, в силу метода математиче-ской индукции, утверждение верно для любого на- турального n. ПРИМЕР 5 Доказать, что для любого натурального n спра-ведливо равенство: 13+23+33+…+n3=n2(n+1)2/4. Решение: 1) Пусть n=1. Тогда Х1=13=12(1+1)2/4=1. Мы видим, что при n=1 утверждение верно. 2) Предположим, что равенство верно при n=k Xk=k2(k+1)2/4. 3) Докажем истинность этого ут-верждения для n=k+1, т.е. Хk+1=(k+1)2(k+2)2/4. Xk+1=13+23+…+k3+(k+1)3=k2(k+1)2/4+(k+1)3=(k2(k++1)2+4(k+1)3)/4=(k+1)2(k2+4k+ 4)/4=(k+1)2(k+2)2/4. Из приведённого доказательства видно, что ут-верждение верно при n=k+1, следовательно, равен-ство верно при любом натуральном n. ПРИМЕР 6 Доказать, что ((23+1)/(23-1))(((33+1)/(33-1))(…(((n3+1)/(n3-1))= =3n(n+1)/2(n2+n+1), где n>2. Решение: 1) При n=2 тождество выглядит: (23+1)/(23- 1)=(3(2(3)/2(22+2+1), т.е. оно верно. 2) Предположим, что выражение верно при n=k (23+1)/(23-1)(…((k3+1)/(k3-1)=3k(k+1)/2(k2+k+1). 3) Докажем верность выражения при n=k+1. (((23+1)/(23-1))(…(((k3+1)/(k3-1)))((((k+1)3+ +1)/((k+1)3-1))=(3k(k+1)/2(k2+k+1))(((k+2)((k+ +1)2-(k+1)+1)/k((k+1)2+(k+1)+1))=3(k+1)(k+2)/2( (((k+1)2+(k+1)+1). Мы доказали справедливость равенства и при n=k+1, следовательно, в силу метода математиче-ской индукции, утверждение верно для любого n>2 ПРИМЕР 7 Доказать, что 13-23+33-43+…+(2n-1)3-(2n)3=-n2(4n+3) для любого натурального n. Решение: 1) Пусть n=1, тогда 13-23=-13(4+3); -7=-7. 2) Предположим, что n=k, тогда 13-23+33-43+…+(2k-1)3-(2k)3=-k2(4k+3). 3) Докажем истинность этого ут-верждения при n=k+1 (13-23+…+(2k-1)3-(2k)3)+(2k+1)3-(2k+2)3=-k2(4k+3)+ +(2k+1)3-(2k+2)3=-(k+1)3(4(k+1)+3). Доказана и справедливость равенства при n=k+1, следовательно утверждение верно для лю-бого натурального n. ПРИМЕР 8 Доказать верность тождества (12/1(3)+(22/3(5)+…+(n2/(2n-1)((2n+1))= =n(n+1)/2(2n+1) для любого натурального n. Решение: 1) При n=1 тождество верно 12/1(3=1(1+1)/2(2+1). 2) Предположим, что при n=k (12/1(3)+…+(k2/(2k-1)((2k+1))=k(k+1)/2(2k+1). 3) Докажем, что тождество верно при n=k+1. (12/1(3)+…+(k2/(2k-1)(2k+1))+(k+1)2/(2k+1)(2k+3)= =(k(k+1)/2(2k+1))+((k+1)2/(2k+1)(2k+3))=((k+ +1)/(2k+1))(((k/2)+((k+1)/(2k+3)))=(k+1)(k+2)( ((2k+1)/2(2k+1)(2k+3)=(k+1)(k+2)/2(2(k+1)+1). Из приведённого доказательства видно, что ут-верждение верно при любом натуральном n. ПРИМЕР 9 Доказать, что (11n+2+122n+1) делится на 133 без остатка. Решение: 1) Пусть n=1, тогда 113+123=(11+12)(112-132+122)=23(133. Но (23(133) делится на 133 без остатка, значит при n=1 утверждение верно; А(1) истинно. 2) Предположим, что (11k+2+122k+1) делится на 133 без остатка. 3) Докажем, что в таком случае (11k+3+122k+3) делится на 133 без остатка. В самом деле 11k+3+122л+3=11(11k+2+122(122k+1=11(11k+2+ +(11+133)(122k+1=11(11k+2+122k+1)+133(122k+1. Полученная сумма делится на 133 без остатка, так как первое её слагаемое делится на 133 без ос-татка по предположению, а во втором одним из множителей выступает 133. Итак, А(k)(А(k+1). В силу метода математической индукции утвержде-ние доказано. ПРИМЕР 10 Доказать, что при любом n 7n-1 делится на 6 без остатка. Решение: 1) Пусть n=1, тогда Х1=71-1=6 де-лится на 6 без остатка. Значит при n=1 утвержде-ние верно. 2) Предположим, что при n=k 7k-1 делится на 6 без остатка. 3) Докажем, что утверждение справедливо для n=k+1. Xk+1=7k+1-1=7(7k-7+6=7(7k-1)+6. Первое слагаемое делится на 6, поскольку 7k-1 делится на 6 по предположению, а вторым слага-емым является 6. Значит 7n-1 кратно 6 при любом натуральном n. В силу метода математической ин-дукции утверждение доказано. ПРИМЕР 11 Доказать, что 33n-1+24n-3 при произвольном на-туральном n делится на 11. Решение: 1) Пусть n=1, тогда Х1=33-1+24-3=32+21=11 делится на 11 без остат-ка. Значит, при n=1 утверждение верно. 2) Предположим, что при n=k Xk=33k-1+24k-3 делится на 11 без остатка. 3) Докажем, что утверждение верно для n=k+1. Xk+1=33(k+1)-1+24(k+1)-3=33k+2+24k+1=33(33k-1+24(24k-3= =27(33k-1+16(24k-3=(16+11)(33k-1+16(24k-3=16(33k-1+ +11(33k-1+16(24k-3=16(33k-1+24k-3)+11(33k-1. Первое слагаемое делится на 11 без остатка, поскольку 33k-1+24k-3 делится на 11 по предположе-нию, второе делится на 11, потому что одним из его множителей есть число 11. Значит и сумма де-лится на 11 без остатка при любом натуральном n. В силу метода математической индукции утвер-ждение доказано. ПРИМЕР 12 Доказать, что 112n-1 при произвольном нату-ральном n делится на 6 без остатка. Решение: 1) Пусть n=1, тогда 112-1=120 делится на 6 без остатка. Значит при n=1 утвержде-ние верно. 2) Предположим, что при n=k 112k-1 делится на 6 без остатка. 3) Докажем, что утверждение верно при n=k+1 112(k+1)-1=121(112k-1=120(112k+(112k-1). Оба слагаемых делятся на 6 без остатка: пер-вое содержит кратное 6-ти число 120, а второе де-лится на 6 без остатка по предположению. Значит и сумма делится на 6 без остатка. В силу метода математической индукции утверждение доказано. ПРИМЕР 13 Доказать, что 33n+3-26n-27 при произвольном натуральном n делится на 262(676) без остатка. Решение: Предварительно докажем, что 33n+3-1 делится на 26 без остатка. 1) При n=0 33-1=26 делится на 26 2) Предположим, что при n=k 33k+3-1 делится на 26 3) Докажем, что утверждение верно при n=k+1. 33k+6-1=27(33k+3-1=26(33л+3+(33k+3-1) –делится на 26 Теперь проведём доказательство утвер-ждения, сформулированного в условии задачи. 1) Очевидно, что при n=1 утвер-ждение верно 33+3-26-27=676 2) Предположим, что при n=k выражение 33k+3-26k-27 делится на 262 без остатка. 3) Докажем, что утверждение верно при n=k+1 33k+6-26(k+1)-27=26(33k+3-1)+(33k+3-26k-27). Оба слагаемых делятся на 262; первое делится на 262, потому что мы доказали делимость на 26 выражения, стоящего в скобках, а второе делится по предположению индукции. В силу метода мате-матической индукции утверждение доказано. ПРИМЕР 14 Доказать, что если n>2 и х>0, то справедливо неравенство (1+х)n>1+n(х. Решение: 1) При n=2 неравенство справед-ливо, так как (1+х)2=1+2х+х2>1+2х. Значит, А(2) истинно. 2) Докажем, что А(k)(A(k+1), если k> 2. Предположим, что А(k) истинно, т.е., что справедливо неравенство (1+х)k>1+k(x. (3) Докажем, что тогда и А(k+1) истинно, т.е., что справедливо неравенство (1+x)k+1>1+(k+1)(x. В самом деле, умножив обе части неравенства (3) на положительное число 1+х, получим (1+x)k+1>(1+k(x)(1+x). Рассмотрим правую часть последнего неравен- ства; имеем (1+k(x)(1+x)=1+(k+1)(x+k(x2>1+(k+1)(x. В итоге получаем, что (1+х)k+1>1+(k+1)(x. Итак, А(k)(A(k+1). На основании принципа математической индукции можно утверждать, что неравенство Бернулли справедливо для любого n> 2. ПРИМЕР 15 Доказать, что справедливо неравенство (1+a+a2)m> 1+m(a+(m(m+1)/2)(a2 при а> 0. Решение: 1) При m=1 (1+а+а2)1> 1+а+(2/2)(а2 обе части равны. 2) Предположим, что при m=k (1+a+a2)k>1+k(a+(k(k+1)/2)(a2 3) Докажем, что при m=k+1 не-равенство верно (1+a+a2)k+1=(1+a+a2)(1+a+a2)k>(1+a+a2)(1+k(a+ +(k(k+1)/2)(a2)=1+(k+1)(a+((k(k+1)/2)+k+1)(a2+ +((k(k+1)/2)+k)(a3+(k(k+1)/2)(a4> 1+(k+1)(a+ +((k+1)(k+2)/2)(a2. Мы доказали справедливость неравенства при m=k+1, следовательно, в силу метода математиче-ской индукции, неравенство справедливо для лю-бого натурального m. ПРИМЕР 16 Доказать, что при n>6 справедливо неравенство 3n>n(2n+1. Решение: Перепишем неравенство в виде (3/2)n>2n. 1) При n=7 имеем 37/27=2187/128>14=2(7 неравенство верно. 2) Предположим, что при n=k (3/2)k>2k. 3) Докажем верность неравен-ства при n=k+1. 3k+1/2k+1=(3k/2k)((3/2)>2k((3/2)=3k>2(k+1). Так как k>7, последнее неравенство очевидно. В силу метода математической индукции неравен-ство справедливо для любого натурального n. ПРИМЕР 17 Доказать, что при n>2 справедливо неравенство 1+(1/22)+(1/32)+…+(1/n2)<1,7-(1/n). Решение: 1) При n=3 неравенство верно 1+(1/22)+(1/32)=245/180<246/180=1,7-(1/3). 2) Предположим, что при n=k 1+(1/22)+(1/32)+…+(1/k2)=1,7-(1/k). 3) Докажем справедливость не- равенства при n=k+1 (1+(1/22)+…+(1/k2))+(1/(k+1)2)<1,7-(1/k)+(1/(k+1)2). Докажем, что 1,7-(1/k)+(1/(k+1)2)<1,7-(1/k+1)( ((1/(k+1)2)+(1/k+1)<1/k((k+2)/(k+1)2<1/k( (k(k+2)<(k+1)2(k2+2k