Chuprigin_O_A_-_Matematicheskiy_analiz_predel_nepreryvnost_differentsiruemost_pdf

научной практике называют обычно индуктивным методом (индукцией). Ученый на основании отдельных наблюдений, экспериментов создает «по индукции» общую теорию или гипотезу, которые объясняют эти наблюдения. Понятно, что сделать общий вывод на основе отдельных фактов не всегда удается, в этом смысле «индукция» не более чем чья-то догадка. Индукция может привести как к истинным, так и к ошибочным выводам (см., например, утверждение Ферма на с. 34). «Математическая индукция» отличается от простой «индукции» тем, что это не догадки и предположения, а строгий метод доказательств утверждений. Этот метод назван «индукцией» только потому, что сначала, перед тем как его применить, необходимо установить «÷òî» мы собираемся доказывать. Вот это «÷òî» обычно устанавливается в индуктивном исследовании с помощью простой индукции, а математическая индукция выступает как заключительный шаг.

	n		1
	Например, доказать соотношение k2			n(n 1)(2n 1) ìåòî-
			6
	k	1

дом математической индукции не составляет особых трудностей. Если же правая часть этого равенства неизвестна, а требуется найти выражение для суммы квадратов, то сразу применить метод математической индукции нельзя, ибо не установлено, «÷òî» мы должны доказать, т. е. сначала нужно угадать правую часть равенства. В данном случае угадать «по индукции» вид правой части труднее, чем доказать готовую формулу. Можно подумать, что индуктивная гипотеза возникает при анализе отдельных фактов случайно. «Однако такие случаи встречаются только людям, которые их заслуживают», — утверждал Лагранж.

Заметим, что современники Паскаля редко применяли в доказательствах метод математической индукции и не чувствовали в этом методе особой нужды. Неполной индукцией (когда на основании разбора отдельных (не всех) случаев делались общие выводы) пользовались Ньютон, Эйлер. По этому поводу Лейбниц писал в 1695 г.: «Признаюсь, что высоко ценю прилежание тех, которые всегда стараются свести строжайшим образом к первоосновам и нередко уделяют все свое внимание таким вещам; но я не советовал бы вести рассуждения так, чтобы излишняя скрупулезность служила преградой искусству нахождения решения или чтобы по такого рода основаниям отказались от блестящих открытий и лишали самих себя их результатов».

42

Понятно, что при рассмотрении простых утверждений ограничиваются неполной индукцией, о чем свидетельствует употребление слов «и т. д.». Однако в математических доказательствах следует отдать преимущество строгости рассуждений, дабы избежать ошибок. Иногда, правда, ситуация столь очевидна, что подробные рассуждения являются ненужным педантизмом. Но во всяком случае надо руководствоваться указаниями Гильберта: математическое доказательство должно быть строгим, полным и понятным.

1.4.3. Упражнения

1. Методом математической индукции докажите, что n верны равенства:

n	1		n			1				n
1) k(k 1)		n(n 1)(n 2);	2)								.
i 1	3		k 1 (4k		3)(4k 1)					4n 1
					n	1
2. Найдите простую формулу для суммы								и докажи-
						2
					k 1	4k	1
òå åå.
		n
3. Найдите выражение для k2 и докажите соответствующее
		k 1
равенство.
			n			n
(Указание: рассмотрите отношение k2					k.)
			k 1		k 1

4. Заметим, что

1 1,

1 4 (1 2), 1 4 9 1 2 3,

1 – 4 9 – 16 (1 2 3 4).

Сформулируйте общее правило, соответствующее этим примерам, и докажите его методом математической индукции.

5. Докажите неравенства:
1)	(2n 1) !!				1		, n ;
	(2n) !!				2n 1
2) 2n n3, åñëè n 10.
Ó ê à ç à í è å:							1		3			1		3
			2		1					1			.
							10
												n

43

6. Докажите, что n :

à) 62n 2 3n 1 3n 1 кратно 11; б) 11n 1 122n 1 кратно 133.

7. Докажите, что при любом натуральном n 1 число 22n 1 оканчивается цифрой 7.

8.Докажите, что любую сумму денег, большую 7 копеек, можно разменять только трехкопеечными и пятикопеечными монетами.

9.Докажите, что любое положительное целое число a (a 1) можно записать как произведение простых чисел.

10. Докажите, что числа Фибоначчи (см. пример 3) удовле-

творяют условию Fn 1Fn 1 Fn2 ( 1)n (n ) (заметим, что мето-

дом математической индукции можно доказать матричное тождество

1	1 n	F		1	F
			n		n
1	0		Fn		Fn 1

и, если найти определители обеих частей этого равенства, полу- чить предыдущее утверждение).

11. Пользуясь методом математической индукции, докажите следующую теорему Никомаха (около 100 г. н. э.):

13 1,

23 3 5,

33 7 9 11, 43 13 15 17 19 è ò. ä.

12. Докажите, что

									n							n
									(1 ai) 1 ai,
									i 1							i 1
åñëè 0 ai		1			i.
13. Следующее доказательство по индукции выглядит кор-
ректным.
«Теорема:					1				1		...				1			3		1	».
			1 2 2 3												(n 1)n 2 n
Д о к а з а т е л ь с т в о. Применим индукцию по n. Äëÿ n 1
имеем	1		3			1		, ò. å.			1		1	.
1 2		2			1				2 2

44

Предполагая, что теорема верна для n, проверяем равенство

äëÿ n 1:
	1		1				...											1											1										3				1				1
1 2 2 3													(n 1)n n(n 1) 2 n n(n 1)
										3					1						1					1								3							1			,
										2						n					n						n 1							2 n 1
что и требовалось доказать.
Но с другой стороны,
										1										1					...								1
										1 2 2 3																					(n 1)n
			1					1						1						1													1								1						1
																								...																		1						.
																																															n
			1 2											2 3															n 1												n

Где ошибка в приведенном доказательстве?

1.5. БИНОМ НЬЮТОНА

1.5.1. Биномиальные коэффициенты

r

Определим символ для всех действительных чисел r è öå-

k

лых чисел k следующим образом:

r	r(r 1) ... (r k 1)				r 1	j	,	åñëè k 0,
			k !		j
				1 j k
k			åñëè k 0.
	0,

r

Подчеркнем, что символ не имеет горизонтальной черты

k

посередине — это не дробь!

В частных случаях имеем:
r		1 (по определению пустого произведения																		a		1),
																					j
	0																	1 j 0
		r		r			r(r		1)		r			r(r		1)(r		2)
			r,							,									.
								2								6
			1		2							3

45

r

Величины называются биномиальными коэффициента-

k

ìè. Биномиальные коэффициенты имеют чрезвычайно широкое применение в комбинаторике, теории алгоритмов, теории вероятностей и иных разделах математики. Эти коэффициенты и многие их свойства известны издавна, письменные сведения о них встречаются в десятом столетии. Для малых значений k биномиальные коэффициенты были известны значительно раньше,

r

их использовали греческие и римские авторы. Обозначение ,

k

берущее начало от Эйлера, обычно приписывают Раабе (1851), однако оно было введено Эттинсхаузеном в его книге «Комбинаторный анализ» (1826).

В большинстве случаев, когда мы будем иметь дело с биномиальными коэффициентами, числа r è k будут целыми и неотрицательными, причем r k.

Итак, пусть n k 0, причем n è k — целые числа. Везде в дальнейшем будем считать, если это не оговорено особо, что указанные условия выполняются. Тогда для биномиального коэф-

n

фициента используют обычно в отечественной литературе

k

обозначение Cnk (читается: «число сочетаний из n ïî k»). Таким образом,

n

n(n

1) ... (n

1)

k

1

k

n

j

Cnk

.

(1.3)

k !

j

k

j 1

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

1. Представление с помощью факториалов. Непосредственно из определения биномиальных коэффициентов (1.3) следует, что

	n		n !
	Cnk			.	(1.4)
			k !(n k) !
	k

46

2. Симметрия. Из представления (1.4) следует, что

n		n
Cnk Cnn k èëè		.
k	n k

Таким образом, в частности,

Cn0 Cnn 1,

Cnn 1 Cn1 n,

Cnn 2 Cn2 n(n 1) . 2

3. Формула сложения, или правило Паскаля. Имеет место следующее соотношение:

C k C k 1

C k

n

n

n 1

(1.5)

èëè

.

n

n

n 1

k

k

k

1

Правило Паскаля легко проверяется непосредственно, если воспользоваться формулой (1.4) и основным тождеством для факториалов (n 1) n ! (n 1) !.

Действительно,

Cnk Cnk 1

n !

n !

k !(n k) !

(k 1) !(n k 1) !

n !

1

1

(k 1) !(n k) !

k n k 1

n !

n 1

(n 1) !

Cnk 1.

(k 1) !(n k) ! k(n k 1)

k !(n k 1) !

r

r

r 1

имеет место

Заметим, что соотношение

k

k

k 1

при любых действительных r.

Правило Паскаля дает простой способ построения таблицы биномиальных коэффициентов. Эта таблица содержалась в одной работе Паскаля (1653) и известна под названием треугольника Паскаля. Однако приоритет в открытии таблицы биномиальных коэффициентов Паскалю не принадлежит, ибо такая таблица встречается значительно раньше, например в трактате китайского математика Чжу Ши-чжи (1303).

47

Треугольник Паскаля коэффициентов Cnk (0 k n 10) имеет следующий вид:

n\k	0	1	2	3	4	5	6	7	8	9	10
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	210	252	210	120	45	10	1

Первые и последние элементы каждой строки равны 1, так как Cn0 Cnn 1 n, каждый иной элемент таблицы, согласно

правилу Паскаля, равен сумме элемента, стоящего непосредственно над ним, и элемента, стоящего над ним слева.

4. Формула суммирования. Последовательным применением правила Паскаля легко показать, что

m

Cn0 Cn1 1 ... Cnm m Cnm m 1 èëè Cnk k Cnm m 1. (1.6) k 0

Действительно,

Cn0 Cn1 1 Cn0 1 Cn1 1 Cn1 2, Cn1 2 Cn2 2 Cn2 3, Cn2 3 Cn3 3 Cn3 4 è ò. ä.

Íà m-м шаге получим Cnm m1 Cnm m Cnm m 1, что и требовалось

доказать.

Из формулы (1.6), используя симметрию биномиальных коэффициентов, имеем

m	m	m	0	1	...	n m	n m	m 1
Cm	Cm 1	... Cn	Cm	Cm 1		Cn	Cn 1	Cn 1
				n
			èëè Ckm Cnm 11.					(1.7)

k m

48

Проиллюстрируем на примерах применение формулы (1.7).

Пример:

	n	n
	Найти: a) k; á) k2.
	k 1	k 1
	à) Òàê êàê Cm1 m	m , òî èç (1.7) ïðè m 1 имеем
	n	n			(n 1)n
	k Ck1 Cn2 1						.
				2
	k 1	k 1
	б) Убедимся сначала в том, что k2			2C2k Ck1 k 2.
	Действительно, 2C2k Ck1 2		k(k 1)			k k2.
		2

Тогда, используя формулу (1.7) при m 1 è m 2, получим

n n n n n

k2 1 k2 1 (2C2k Ck1 ) 1 2 C2k Ck1 C11

k 1 k 2 k 2 k 2 k 1

1 2Cn3 1	Cn2 1	1 2		(n 1)n(n 1)			(n 1)n
		6				2
			(n 1)n(2n 1)		.
		6
								n

Аналогичным способом можно получить значение суммы kp,

k 1

так как любой многочлен a0 a1k ... apkp можно представить в виде b0Ck0 b1Ck1 ... bpCkp с соответствующим образом подобран-

ными коэффициентами b0, b1, ..., bp. Например, k3 6Ck3 6C2k Ck1, k4 24Ck4 36Ck3 14C2k Ck1 ( k 4).

1.5.2. Бином Ньютона

Нам известны выражения для второй и третьей степеней дву- члена (бинома) a b, которые можно записать через биномиальные коэффициенты:

2

(a b)2 a2 2ab b2 C20a2 C21a1b1 C22b2 C2ka2 kbk,

k 0

3

(a b)3 a3 3a2b 3ab2 b3 C3ka3 kbk.

k 0

49

Разложение по степеням чисел a è b выражения (a b)n при любом натуральном n можно получить путем перемножения одинаковых множителей. Очевидно, что с ростом показателя степени трудоемкость такой операции резко возрастает. Оказывается, что полученные выше две формулы можно естественно распространить на любую степень n. Имеет место следующая теорема.

Теорема 1 (биномиальная теорема). Åñëè n , òî

n
(a b)n Cnkan kbk,		(1.8)
k	0

ãäå Cnk — биномиальные коэффициенты (отсюда и следует их название), ò. å.

	Cnk	n !	(k 0, 1, 2, ..., n).
		k !(n k) !

Доказательство проведем методом математической индукции. При n 1, 2, 3 наше утверждение имеет место, как видно из сказанного выше. Покажем справедливость индуктивного пере-

õîäà îò n ê n 1:
		n
(a b)n 1 (a b)n(a b)		Cnkan kbk	(a b)
	k 0
n	n
Cnkan 1 kbk Cnkan kbk 1
k 0	k 0
n	n 1
Cn0an 1 Cnkan 1 kbk Cnkan kbk 1 Cnnbn 1.
k 1	k 0
Если теперь увеличить на 1 индекс суммирования во второй
сумме и учесть равенства Cn0	Cn0 1, Cnn Cnn 11, а также восполь-

зоваться правилом Паскаля (1.5), то можно записать

n n

(a b)n 1 Cn0 1an 1 Cnkan 1 kbk Cnk 1an k 1bk Cnn 11bn 1

k 1	k 1
n

Cn0 1an 1 (Cnk Cnk 1 )an 1 kbk Cnn 11bn 1

	k 1
n	n 1

Cn0 1an 1 Cnk 1an 1 kbk Cnn 11bn 1 Cnk 1an 1 kbk. k 1 k 0

50

Замечание. Иногда формулу (1.8) записывают в другом виде:

(a b)n	n ! aibk	(k, i 0).	(1.9)
k i n i ! k !

Формула (1.8) при малых n была известна в древние времена. Для любого натурального n биномиальную формулу получил зимой 1665 г. Ньютон; еще раньше ей пользовался Паскаль. Уместно отметить, что у Ньютона в действительности был значительно более общий результат. Он получил, и в этом его основная заслуга, разложение бинома (a b)p, ãäå p — произвольное число, не обязательно натуральное. При произвольном показателе p сумма в правой части биномиальной формулы содержит бесконечное число слагаемых, является так называемым бесконечным рядом.

Подготовленная Ньютоном в 1666 г. рукопись, содержащая среди других результатов и биномиальную теорему, в свое время не была опубликована; она увидела свет только через 300 лет. Однако об открытии биномиальной теоремы Ньютон сообщил в письме к Лейбницу в 1676 г. Впервые биномиальная теорема была опубликована в трактате Валлиса «Алгебра, исторический и практический трактат» (1685). В общем случае (произвольный показатель) привести доказательство биномиальной теоремы первым попробовал Эйлер (1774), однако его доказательству не хватило строгости. Только в 1812 г. Гаусс привел первое строгое доказательство биномиальной формулы при произвольном показателе. Что касается самого Ньютона, то он, по-видимому, не располагал настоящим доказательством (в то время не вполне осознавали необходимость строгого доказательства).

Известны обобщения биномиальной теоремы. Если, например, нужно возвести в степень сумму k слагаемых (k 2), то используют следующую полиномиальную теорему.

Теорема 2. Если n — натуральное число и k 2, òî

	k	n					(n)	x"1 x"2		"k ,
	x	!				A			... x
	i						"1"2..."k	1 2		k
i 1		"	"	...	"	n
		1	2		k

где суммирование ведется по всем целым неотрицательным1, 2, ..., k, а полиномиальные коэффициенты

	A"(n)" ..."		n !	.
			k
	1 2	k
			#("i) !
			i 1

51