Книги по разным темам Pages:     | 1 |   ...   | 4 | 5 | 6 | 7 | 8 |   ...   | 76 |

Сформулируем этот принцип следующим образом. Предположим, что требуется установить справедливость бесконечной последовательности математических предложений A1, A2, A3,..., которые все, совместно взятые, образуют некоторое общее предложение A. Допустим, что а) проведено математическое рассуждение, показывающее, что если верно Ar, то верно и Ar+1, каково бы ни было натуральное число r, и б ) установлено, что A1 верно. Тогда все предложения нашей последовательности верны и, следовательно, предложение A доказано.

Мы примем принцип индукции без колебаний (так же как мы принимаем все правила обыкновенной логики) и будем его рассматривать как основной принцип, на котором строится математическое доказательство. В самом деле, мы можем установить справедливость каждого утверждения An, исходя из допущения б) о том, что A1 справедливо, и, многократно пользуясь допущением а), последовательно установим справедливость утверждений A2, A3, A4, и т. д., пока не достигнем утверждения An. Принцип математической индукции вытекает, таким з 2 БЕСКОНЕЧНОСТЬ СИСТЕМЫ НАТУРАЛЬНЫХ ЧИСЕЛ образом, из того факта, что за каждым натуральным числом r следует (непосредственно) другое натуральное число r + 1 и что, отправляясь от натурального числа 1, можно после конечного числа таких переходов достигнуть любого натурального числа n.

Часто принцип математической индукции применяют без явного о том упоминания или же просто он скрывается за формулой ли так далее. Такая скрытая форма применения принципа индукции в особенности свойственна преподаванию элементарной математики. Но при доказательстве иных, более тонких и более глубоких теорем этим принципом неизбежно приходится пользоваться явно. Мы приведем далее некоторое число относящихся сюда простых и все же не совсем тривиальных примеров.

2. Арифметическая прогрессия. Каково бы ни было значение n, n(n + 1) сумма 1 + 2 + 3 +... + n первых n натуральных чисел равна.

Чтобы доказать эту теорему по принципу математической индукции, мы должны для произвольного значения n установить справедливость соотношения An:

n(n + 1) 1 + 2 + 3 +... + n =. (1) а) Если r Ч некоторое натуральное число и если известно, что утверждение Ar справедливо, т. е. если известно, что r(r + 1) 1 + 2 + 3 +... + r =, то, прибавляя к обеим частям последнего равенства по r + 1, мы получаем:

r(r + 1) 1 + 2 + 3 +... + r + (r + 1) = + (r + 1) = r(r + 1) + 2(r + 1) (r + 1)(r + 2) = =, 2 а это как раз и есть утверждение Ar+1.

1 б) Утверждение A1, очевидно, справедливо, так как 1 =. Итак, по принципу математической индукции утверждение An справедливо при любом n, что и требовалось доказать.

Обыкновенно эту теорему доказывают иным способом. Пишут сумму 1 + 2 + 3 +... + n в двух видах:

Sn = 1 + 2 +... + (n - 1) + n и Sn = n + (n - 1) +... + 2 + 1.

Складывая, мы видим, что числа, стоящие на одной вертикали, вместе составляют n + 1, и так как вертикалей всего имеется n, то отсюда 38 НАТУРАЛЬНЫЕ ЧИСЛА гл. I следует, что 2Sn = n(n + 1), и остается еще разделить на 2.

Из формулы (1) сразу же вытекает общая формула для суммы (n + 1) первых членов любой арифметической прогрессии:

(n + 1)(2a + nd) Pn = a + (a + d) + (a + 2d) +... + (a + nd) =. (2) В самом деле, n(n + 1)d Pn = (n + 1)a + (1 + 2 +... + n)d = (n + 1)a + = 2(n + 1)a + n(n + 1)d (n + 1)(2a + nd) = =.

2 В случае, когда a = 0, d = 1, последнее соотношение превращается в соотношение (1).

3. Геометрическая прогрессия. Таким же образом можно рассуждать и по поводу геометрической прогрессии (в общем виде). Мы покажем, что, каково бы ни было n, 1 - qn+Gn = a + aq + aq2 +... + aqn = a. (3) 1 - q (Мы предполагаем, что q = 1: иначе правая часть (3) лишена смысла.) Наше утверждение, несомненно, справедливо при n = 1, так как в этом случае a(1 - q2) a(1 + q)(1 - q) G1 = a + aq = = = a(1 + q).

1 - q 1 - q И если мы допустим, что 1 - qr+Gr = a + aq +... + aqr = a, 1 - q то, как следствие, отсюда немедленно вытекает:

Gr+1 = (a + aq +... + aqr) + aqr+1 = Gr + aqr+1 = 1 - qr+1 (1 - qr+1) + qr+1(1 - q) = a + aqr+1 = a = 1 - q 1 - q 1 - qr+1 + qr+1 - qr+2 1 - qr+= a = a.

1 - q 1 - q Но это как раз и есть утверждение (3) при n = r + 1. Доказательство закончено.

В элементарных учебниках дается другое доказательство. Положим Gn = a + aq +... + aqn.

Умножая обе части на q, получим qGn = aq + aq2 +... + aqn+1.

з 2 БЕСКОНЕЧНОСТЬ СИСТЕМЫ НАТУРАЛЬНЫХ ЧИСЕЛ Вычитая затем последнее равенство из предпоследнего, получаем далее Gn - qGn = a - aqn+1, (1 - q)Gn = a(1 - qn+1), 1 - qn+Gn = a.

1 - q 4. Сумма n первых квадратов. Следующее интересное применение принципа математической индукции относится к сумме n первых квадратов. Путем проб мы устанавливаем (по крайней мере для нескольких небольших значений n), что n(n + 1)(2n + 1) 12 + 22 + 32 +... + n2 =, (4) после чего естественно высказать в виде догадки утверждение, что эта замечательная формула справедлива при всех целых положительных значениях n. Чтобы доказать это, воспользуемся опять методом математической индукции. Заметим прежде всего, что если утверждение An, которое заключается как раз в соотношении (4), справедливо при n = r, так что r(r + 1)(2r + 1) 12 + 22 + 32 +... + r2 =, то, прибавляя к обеим частям по (r + 1)2, мы получаем r(r + 1)(2r + 1) 12 + 22 +... + r2 + (r + 1)2 = + (r + 1)2 = r(r + 1)(2r + 1) + 6(r + 1)2 (r + 1)[r(2r + 1) + 6(r + 1)] = = = 6 (r + 1)(2r2 + 7r + 6) (r + 1)(r + 2)(2r + 3) = =, 6 а это и есть утверждение Ar+1, так как оно получается из соотношения (4) посредством подстановки r + 1 вместо n. Чтобы закончить доказательство, достаточно обратить внимание на то, что утверждение A1, которое сводится к равенству 1(1 + 1)(2 + 1) 12 =, справедливо. Итак, соотношение (4) верно при всех значениях n.

Подобного же рода формулы можно написать для сумм третьих и четвертых степеней, вообще для сумм вида 1k + 2k + 3k +... + nk, где k Ч произвольное целое положительное число. В качестве упражнения читатель может доказать с помощью математической индукции формулу n(n + 1) 13 + 23 + 33 +... + n3 =. (5) 40 НАТУРАЛЬНЫЕ ЧИСЛА гл. I Необходимо заметить в заключение, что, хотя принципа математической индукции совершенно достаточно для того, чтобы доказать формулу (5) Ч раз она уже написана, однако доказательство не дает решительно никаких указаний, как прийти к самой этой формуле: почему именно нужно догадываться, что сумма n первых кубов равна выраже n(n + 1) нию, а не какому-нибудь иному в таком же роде, например, n(n + 1) 19n2 - 41n + или, и т. д. Выбор велик! Тот факт, что 3 доказательство теоремы заключается в применении таких-то простых логических правил, не оказывает ни малейшего влияния на творческое начало в математике, роль которого Ч делать выбор из бесконечного множества возникающих возможностей. Вопрос о том, как возникает гипотеза (5), принадлежит к той области, в которой нет никаких общих правил; здесь делают свое дело эксперимент, аналогия, конструктивная индукция. Раз только правильная гипотеза сформулирована, принципа математической индукции часто бывает достаточно, чтобы теорема была доказана. Но так как само такое доказательство никак не указывает пути к открытию, то его лучше было бы называть проверкой.

*5. Одно важное неравенство. В следующей главе нам понадобится неравенство (1 + p)n 1 + np, (6) имеющее место при всяком p, удовлетворяющем условию p > -1, и при любом целом положительном значении n. (Ради общности мы предвосхищаем здесь применение отрицательных и нецелых чисел, предполагая, что p может быть любым числом, большим чем -1. Доказательство неравенства одно и то же, независимо от того, каково число p.) Мы воспользуемся и на этот раз математической индукцией.

а) Если верно, что (1 + p)r 1 + rp, то, умножая обе части неравенства на положительное число 1 + p, мы получаем:

(1 + p)r+1 1 + rp + p + rp2.

Отбрасывая вовсе положительный член rp2, мы только усилим это неравенство; итак, (1 + p)r+1 1 + (r + 1)p.

Полученный результат показывает, что неравенство (6) имеет место и при n = r + 1.

б) Совершенно очевидно, что (1 + p)1 1 + p. Таким образом, доказательство закончено.

Ограничение, заключающееся в условии p > -1, существенно. Если p < -1, то 1 + p отрицательно, и рассуждение а) отпадает, так как при умножении обеих частей неравенства на отрицательное число знак з 2 БЕСКОНЕЧНОСТЬ СИСТЕМЫ НАТУРАЛЬНЫХ ЧИСЕЛ неравенства должен измениться. (Например, умножая обе части неравенства 3 > 2 на -1, мы получили бы -3 > -2, а это неверно.) *6. Биномиальная теорема. Часто бывает нужно написать в раскрытом виде выражение для n-й степени бинома (a + b)n. Непосредственное вычисление показывает, что при n = 1 (a + b)1 = a + b, при n = 2 (a + b)2 = (a + b)(a + b) = = a(a + b) + b(a + b) = a2 + 2ab + b2, при n = 3 (a + b)3 = (a + b)(a + b)2 = = a(a2 + 2ab + b2) + b(a2 + 2ab + b2) = a3 + 3a2b + 3ab2 + b3, и так далее. Но какой общий закон скрывается за словами ли так далее Проанализируем процесс вычисления (a + b)2. Так как (a + b)2 = = (a + b)(a + b), то мы получили выражение для (a + b)2, умножая каждый член выражения a + b на a, затем на b и складывая то, что получилось. Ту же процедуру пришлось применить при вычислении (a + b)3 = = (a + b)(a + b)2. Так же точно вычисляются (a + b)4, (a + b)5 и так далее до бесконечности. Выражение для (a + b)n мы получим, умножая выражение (a + b)n-1 сначала на a, потом на b, затем складывая то, что получится. Это приводит к следующей диаграмме:

a + b = a + b (a + b)2 = a2 + 2ab + b(a + b)3 = a3 + 3a2b + 3ab2 + b(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab2 + b4, позволяющей сразу разобраться в общем законе составления коэффициентов в разложении (a + b)n. Мы строим треугольную схему из натуральных чисел, начиная с коэффициентов 1, 1 двучлена a + b таким образом, что каждое число в треугольнике является суммой двух чисел, стоящих над ним в предыдущей строке (слева и справа). Такая схема известна под названием треугольника Паскаля.

1 1 2 1 3 3 1 4 6 4 1 5 10 10 5 1 6 15 20 15 6 1 7 21 35 35 21 7..................................

42 НАТУРАЛЬНЫЕ ЧИСЛА гл. I Коэффициенты в разложении (a + b)n по убывающим степеням a и возрастающим степеням b стоят в n-й строке этой схемы.

Так, например, (a + b)7 = a7 + 7a6b + 21a5b2 + 35a4b3 + 35a3b4 + 21a2b5 + 7ab6 + b7.

С помощью очень сжатых обозначений, использующих нижние и верхние значки (индексы), запишем числа, стоящие в n-й строке треугольника Паскаля, следующим образом:

n n n n n n C0 = 1, C1, C2, C3,..., Cn-1, Cn = 1.

Тогда общей формуле для разложения (a + b)n можно придать вид n n n (a + b)n = an + C1 an-1b + C2 an-2b2 +... + Cn-1abn-1 + bn. (7) Согласно закону, лежащему в основе построения треугольника Паскаля, мы имеем соотношение n n-1 n-Ci = Ci-1 + Ci. (8) В качестве упражнения читатель, имеющий уже некоторый опыт в применении математической индукции, может воспользоваться этим прин1 ципом (и очевидными равенствами C0 = C1 = 1) для доказательства общей формулы n(n - 1)(n - 2)... (n - i + 1) n! n Ci = =. (9) 1 2 3 ... i i!(n - i)! (При любом целом положительном значении n символ n! (читается n-факториал) обозначает произведение n первых натуральных чисел:

n! = 1 2 4 ... n. Удобно положить по определению 0! = 1, чтобы формула (9) оправдывалась также и при i, равном 0 или n.) Выводу этой раскрытой формулы для коэффициентов биномиального разложения иногда дается наименование биномиальной теоремы (см. также стр. 500).

Упражнения. Докажите с помощью метода математической индукции следующие равенства:

1 1 1 n 1) + +... + =.

1 2 2 3 n(n + 1) n + 1 2 3 n n + 2) + + +... + = 2 -.

2 2n 2n 22 1 - (n + 1)qn + nqn+ 3) 1 + 2q + 3q2 +... + nqn-1 =.

(1 - q)n+n - q 4) (1 + q)(1 + q2)(1 + q4)... (1 + q2 ) =.

1 - q Найдите сумму следующих геометрических прогрессий:

1 1 5) + +... +.

1 + x2 (1 + x2)2 (1 + x2)n x x2 xn 6) 1 + + +... +.

1 + x2 (1 + x2)2 (1 + x2)n з 2 БЕСКОНЕЧНОСТЬ СИСТЕМЫ НАТУРАЛЬНЫХ ЧИСЕЛ 2 n x2 - y2 x2 - y2 x2 - y7) + +... +.

x2 + y2 x2 + y2 x2 + yПользуясь формулами (4) и (5), докажите равенства:

(n + 1)(2n + 1)(2n + 3) 8) 12 + 32 +... + (2n + 1)2 =.

9) 13 + 33 +... + (2n + 1)3 = (n + 1)2 (2n2 + 4n + 1).

10) То же самое докажите непосредственно методом математической индукции.

7. Дальнейшие замечания по поводу метода математической индукции. Принцип математической индукции может быть слегка обобщен следующим образом: если имеется последовательность утверждений As, As+1, As+2,..., где s Ч некоторое положительное число, и если а) при всяком значении r s справедливость Ar+1 следует из справедливости Ar, и б) известно, что As справедливо, то все утверждения As, As+1, As+2,... справедливы. Иначе говоря, An справедливо при любом n s. То же самое рассуждение, которое привело нас к обыкновенному принципу математической индукции, пригодно и в данном случае, только последовательность 1, 2, 3,... заменяется на этот раз подобной ей последовательностью s, s + 1, s + 2, s + 3,...

Пользуясь принципом индукции в этой форме, мы можем усилить неравенство (6) на стр. 34, исключая возможность знака равенства. Именно: каково бы ни было p = 0 и > -1 и каково бы ни было целое число n 2, имеет место неравенство (1 + p)n > 1 + np. (10) Доказательство предоставляется читателю.

С принципом математической индукции тесно связан принцип наименьшего целого числа, утверждающий, что во всяком непустом множестве C натуральных чисел имеется наименьшее число. Множество C может быть конечным, как, например, множество 1, 2, 3, 4, 5, или бесконечным, как, например множество всех четных чисел 2, 4, 6, 8, 10,... Множество называется пустым, если оно не содержит ни одного элемента; примером пустого множества может служить множество всех кругов, одновременно являющихся прямыми линиями, или множество натуральных чисел n, удовлетворяющих соотношению n > n. По понятным причинам мы оговариваем в формулировке принципа наименьшего целого числа, что пустые множества исключаются.

Всякое непустое множество C целых чисел непременно содержит хоть одно число, например n, и тогда наименьшее из чисел 1, 2, 3,..., n, принадлежащее множеству C, есть наименьшее целое число множества.

Чтобы уяснить значение этого принципа, следует указать на то, что он, вообще говоря, неверен для множеств, состоящих из нецелых чисел; например, 1 1 множество положительных дробных чисел 1,,,,... не содержит наи2 3 меньшего числа.

Pages:     | 1 |   ...   | 4 | 5 | 6 | 7 | 8 |   ...   | 76 |    Книги по разным темам