Chuprigin_O_A_-_Matematicheskiy_analiz_predel_nepreryvnost_differentsiruemost_pdf

3

2n

k

(k 1)

â) (2j) !!;

æ)

cos

cos

;

j 1

k 1

n

n

4

5

1 3 5 ... (2k 1)

ã) k !!;

ç)

;

2

4 6 ... 2k

k 1

k 1

n

10

(2n 1) !!(2n) !!

ä) (ak ak 1 );

è)

.

(2n) !

k m

n 1

n

å) [k4 (k 1)4 ];

k m

6. Запишите в развернутом виде при n 3 è n 5 следующие двойные суммы:

à)	aij; á)	aij.
	1 i n 1 j i	1 j n 1 i j
7.	Верно ли следующее равенство:
		aij			aij?
	1 i n 1 j i				1 j n j i n
8.	Пусть S — некоторое множество натуральных чисел. Чему
равна сумма 1?
	j S
9.	Запишите с помощью знака последовательность ра-
венств:
	9 1 2 11,
	9 12 3 111,
	9 123 4 1111,
	9 1234 5 11111,
	......................................
	9 123456789 10 1111111111.
10.	Докажите, используя основные свойства сумм, что
	n	nx	n 2	(n 1)x		n	1	x
	jxj								(x 1).
				(x 1)2
	j 0

Указание: ключевые моменты доказательства —

jxj x jxj 1 x (j 1)xj x jxj nxn 1 x xj.

0 j n 0 j n 0 j n 1 0 j n 0 j n 1

32

11. Имеются ли ошибки (и на каком шаге) в следующей цепочке преобразований сумм:

1

a

a

a

i

i

1 n?

a

a

i

1 k n

k

1 i n 1 k n

k

a

1 i n

1 i n

1 i n 1 i n i

n

n

12. Исходя из суммы [(k 1)4 k4 ], найдите k3.

k 0

u 1

n

13. Найдите k4.

k 1

14. Докажите следующие равенства:

à) ai	ak;
R(i)	R(k)
n	m		n
á) a	a		a	;
i 1 i	i 1 i	i m 1 i

n

ä) c cn;

i 1

å) aibi ai bi ;

R(i) R(i) R(i)

					n	n m 1
â) aij aij;				æ) ai ai m 1.
R(i) S (j)		S (j) R(i)			i 1	i m
n		n
ã) cai cn ai;
i 1		i 1
15. Докажите равенство
n !		n !			(n 1) !		(k 1, 2, ..., n).
k !(n k) !		(k 1) !(n k 1) !			k !(n k 1) !

1.4. МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

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

Пусть P(n) — некоторое утверждение о целом числе n. Например, P(n) может быть утверждением «произведение n(n 1) —

четное число» или «при всех натуральных n меньших 5 число 22n 1 является простым».

Чтобы убедиться в справедливости второго утверждения, можно рассмотреть все случаи, вычислив выражение 22n 1 ïðè

n 1, 2, 3, 4 и получив соответственно простые числа 5, 17, 257, 65 337. Здесь существенно, что n пробегает конечное множество

33

значений. Заметим, что известный французcкий математик П. Ферма считал, что числа 22n 1 будут простыми при любом на-

туральном n, и даже бросил вызов Валлису и другим английским математикам, предлагая доказать это утверждение. Однако Эйлер опроверг утверждение Ферма, показав, что число 232 1, соответ-

ствующее n 5, уже не является простым, ибо делится на 641. Доказать подобным образом первое утверждение (о четности произведения n(n 1)) нельзя, ибо перебрать âñå случаи невозможно, так как n пробегает бесконечное множество значений. Одним из важнейших методов доказательства подобных утверждений является метод математической индукции, основанный на одной из аксиом арифметики, называемой принципом

математической индукции.

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

если утверждение P(n), ãäå n , истинно при n m и из того, что оно истинно для n k, где k — любое целое число m, вытекает, что оно истинно для следующего значения n k 1, то утверждение P(n) истинно для любого целого n m.

Таким образом, для доказательства методом математической индукции утверждения P(n) n m нужно сделать два шага:

1)проверить выполнение утверждения P(m);

2)доказать, что k m P(k) P(k 1).

Второй шаг называют индуктивным переходом, или переходом от k ê k 1. Часто удобно при решении задач индуктивный переход рассматривать в виде P(n) P(n 1).

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

В качестве иллюстрации метода математической индукции рассмотрим следующий пример, хорошо известный еще с древних времен.

n

Пример 1. Доказать, что n (2i 1) n2.

i 1

Назовем доказываемое равенство P(n). Нам нужно доказать, что P(n) справедливо для всех натуральных n. В соответствии с указанной выше процедурой, во-первых, убеждаемся в справедливости P(1). Действительно, при n 1 имеем очевидное

34

равенство 1 12. Осталось сделать второй шаг и показать, что при любом натуральном k P(k) P(k 1), иначе говоря, из равенства

k	k 1
(2i 1) k2 следует равенство (2i 1) (k 1)2.
i 1	i 1
Действительно,
k 1	k
(2i 1) (2i 1) 2k 1 k2 2k 1 (k 1)2.
i 1	i 1

Понятно, что можно было бы не вводить новую переменную k, а индуктивный переход рассмотреть в виде P(n) P(n 1), ò. å.

n n 1

(2i 1) n2 (2i 1) (n 1)2.

i 1 i 1

Таким образом, наше утверждение доказано для любого n. Рассмотрим еще одно доказательство приведенного соотношения, используя метод от противного. Предположим, что указанное равенство не выполняется при всех натуральных n, т. е. существуют значения n, для которых имеет место неравенство

n

(2i 1) n2. Пусть ò есть наименьшее из значений ï, äëÿ êî-

i 1

m

торых имеет место неравенство (2i 1) m2, причем m 1.

	i 1
m 1	m

Тогда (2i 1) (2i 1) (2m 1) m2 2m 1 (m 1)2,

i 1 i 1

т. е. неравенство имеет место и для n m – 1, что противоречит тому, что m — наименьшее из значений n. Полученное противоречие завершает доказательство.

Можно дать геометрическую интер-
претацию утверждению, что сумма не-
четных чисел является квадратом: 1 3
5 ... (2n 1) n2.
Показано (для n 8), как квадрат, со-
стоящий из n2 клеток, разбить на группы
ïî 1, 3, 5, ..., 2n 1 клеток (рис. 1.2). Од-
нако этот рисунок можно считать доказа-
тельством только в том случае, если бу-
дет доказано, что данная конструкция	Ðèñ. 1.2

35

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

Замечание 2. Выше мы доказали утверждение о бесконечной совокупности натуральных чисел способом, отличным от метода математической индукции. Это обстоятельство, на первый взгляд, противоречит сказанному в предыдущем замечании. Однако если проанализировать ход доказательства методом от противного, то можно заметить один существенный момент, использованный нами, а именно мы считаем очевидным существование наименьшего из значений n, для которых выполняется неравенство. Ина- че говоря, мы использовали, казалось бы, очевидное утверждение, что любое непустое множество натуральных чисел имеет наименьший элемент. А именно это утверждение равносильно принципу математической индукции!

Пример 2. Доказать неравенство Бернулли

n

n

(1 xi) 1 xi,

i 1

i 1

ãäå âñå xi — числа одного знака, причем xi 1 i.

Обозначим через P(n) доказываемое утверждение. При n 1 имеем, очевидно, 1 x1 1 x1, ò. å. P(1) имеет место. Осталось

показать, что P(n) P(n 1). Действительно, умножив неравенство P(n) íà 1 xn 1 0, получим

n		n
(1 xn 1 ) (1 xi) (1 xi)(1 xn 1 )
i 1		i 1
èëè
n 1	n	n
(1 xi) 1 xi xn 1 xn 1 xi
i 1	i 1	i 1
n 1	n	n 1
1 xi xixn 1 1 xi
i 1	i 1	i 1

(на последнем шаге мы учли, что все произведения xi xn 1 0).

n 1

n

Неравенство (1 xi) 1 xi и есть утверждение P(n 1).

i 1

i 1

Следствие.

(1 x)n 1 xn ïðè x 1 è n .

36

В некоторых случаях полезна следующая эквивалентная форма метода математической индукции.

Чтобы доказать истинность утверждения P(ï) n , нужно сделать два шага:

1)проверить выполнение P(1);

2)доказать, что если P(1), P(2), ..., P(n) справедливы, то

P(n 1) также справедливо, причем это доказательство должно иметь силу n .

Заметим, что случай n m; n, m рассматривается аналогично.

Пример 3. Определим последовательность Фибоначчи F0, F1,

F2, … по правилу F0 0, F1 1, à ïðè n 1 Fn 1 Fn Fn–1 (первые элементы этой последовательности суть 0, 1, 1, 2, 3, 5, 8, 13, 21,...).

	Доказать, что n Fn Ôn–1, ãäå Ô	1
			(1 5).
		2

Будем пользоваться эквивалентной формой метода математической индукции. Пусть P(n) есть утверждение Fn Ôn–1. Ïðè n 1 имеем F1 1, Ô1–1 Ô0 1, ò. å. P(1) справедливо. Утвер-

	ждение P(2) также верно, поскольку F2 1 Ô2–1 Ô	1
			(1 5).
		2

Далее, если P(1), P(2), ..., P(n) справедливы и n 1, то, в частно-

ñòè, P(n 1) è P(n) справедливы, т. е. Fn–1 Ôn–2 è Fn Ôn–1. Складывая эти неравенства, получим

Fn 1 Fn Fn–1 Ôn–1 Ôn–2 Ôn–2(Ô 1).

Важное свойство числа Ф, объясняющее, почему оно играет столь большую роль в этой задаче, состоит в том, что

Ô2 1 (1 2 5 5) 1 (3 5) 1 (1 5) 1 Ô 1.
4	2	2

Используя это равенство и предыдущее соотношение, получа- ем, что Fn 1 Ôn, т. е. утверждение P(n 1).

Заметим, что в доказательстве мы непосредственно проверили утверждения P(1) è P(2). Подобным образом, если бы для доказательства P(n 1) мы использовали утверждения P(n), P(n – 1), P(n – 2), то непосредственной проверке подлежали бы утвержде-

íèÿ P(1), P(2), P(3).

Замечание. Последовательность Фибоначчи была впервые предложена в 1202 г. Леонардо Фибоначчи. О числах Фибоначчи

37

получено много глубоких результатов, находящих применение в разных областях. В частности, с помощью последовательности Фибоначчи доказано (Э. Лукаш), что число 2127 1 является простым.

Число Ф называют «божественной пропорцией» или «отношением золотого сечения». В мире искусства отношение Ф к 1 считается эстетически самым благоприятным. Евклид называл его «отношением крайнего и среднего»; имеет место равенство

A A B , åñëè A Ф (что следует из соотношения Ф2 1 Ô).

B	A	B
	Пример 4. Найти выражение для произведения
		n		1
		1				(n 2)
		k 2		2
				k

èдоказать его с помощью метода математической индукции.

Запишем несколько значений произведения при малых n в виде таблицы:

Значения n		2		3				4			5
Величина произведения		3		2				5			3
		4		3				8			5

Чтобы заметить закономерность перепишем эту таблицу в следующем виде:

n		2			3			4		5
Произведение		3			4			5		6
		4			6			8		10

Теперь уже легко высказать по индукции предположение, что

n		1			n 1
1						.
		k2
k 2					2n

Чтобы лишний раз убедиться в правдоподобии данной гипотезы, найдем произведение при n 6. Правая часть равенства

n 1	ïðè n 6 равна						7			, а левая —
2n							12
		1			1			1					1			1			6 35					7
	1		1			1					1			1												,
								16																12
		4			9								25			36			10 36

т. е. гипотеза подтверждается и при n 6.

38

Теперь применим метод математической индукции для дока-

	n		1
	зательства утверждения P(n), состоящего в том, что 1
			2
	k 2
			k

n 1 . 2n

Ïðè n 2, 3, 4, 5, 6 утверждение Ð(n) справедливо. Покажем, что P(n) P(n 1) n, ò. å.

n

1

n 1

n 1

1

n 2

1

1

.

k2

k2

k 2

2n

k 2

2(n 1)

В самом деле,

n 1				1		n			1						1
	1					1				1
									2							2
k 2				2		k 2
				k					k						(n 1)
			n 1					1						n 2
						1										.
				2n			(n 1)2						2(n 1)

Во многих случаях доказательство методом математической индукции (а именно, индуктивный переход от n ê n 1) реализовать довольно сложно. В качестве иллюстрации такой ситуации рассмотрим вывод часто встречающегося соотношения между средним геометрическим и средним арифметическим неотрицательных чисел.

Пример 5. Доказать следующее утверждение: для любых неотрицательных чисел x1, x2, ..., xn имеет место неравенство

x1x2 ... xn 1 (x1n x2n ... xnn), n

следовательно, если положить xin ài, òî

n a1a2 ... an a1 a2 ... an , n

иначе говоря, среднее арифметическое неотрицательных чисел не меньше среднего геометрического этих чисел.

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

39

Для любых неотрицательных чисел y è z, очевидно, имеет место неравенство

(yn 1 zn 1 )(y z) 0 (n ),

а тогда

yn zn yzn 1 zyn 1.

Возьмем теперь n неотрицательных чисел x1, x2, ..., xn, запишем для них соответствующие неравенства и, сложив их, получим

(x1n x2n) (x1n x3n) (x1n x4n) ... (x1n xnn)

(x2n x3n) (x2n x4n) ... (x2n xnn)

(x3n x4n) ... (x3n xnn)

.......................

(xnn 1 xnn)

(x1x2n 1 x2x1n 1 ) (x1x3n 1 x3x1n 1 ) ... (x1xnn 1 xnx1n 1 )

(x2x3n 1 x3x2n 1 ) ... (x2xnn 1 xnx2n 1 )

.......................

(xn 1xnn 1 xnxnn 11 ).

Приведя подобные члены, получим неравенство

(n 1)(xn xn ...		xn) x (xn 1			xn 1		... xn 1 )
1	2	n	1	2	3		n
			x (xn 1		xn 1	... xn 1 )
			2	1	3		n
			.......................................
			x (xn 1 xn 1				... xn 1 ).
			n	1	2		n 1

Запишем последнее соотношение с помощью сигма-символики

n	n		n
(n 1) xin		xk xin 1		.	(1.2)
i 1	k 1		i 1
			i k

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

	n		1	n
	xi			xin.
	i 1		n i 1

40

	Это неравенство, очевидно, имеет место при n 1 (â ýòîì
случае мы имеем x							1	x ) è ïðè n 2 (в этом случае мы имеем
					1	1		1
x x			1	(x2	x2 ), что равносильно очевидному соотношению
1	2	2		1	2

x21 x22 2x1x2 (x1 x2 )2 0).

Совершим теперь индуктивный переход от n 1 ê n. Предположим, что доказываемое неравенство имеет место для любых n 1 неотрицательных чисел, т. е., в частности, мы можем записать n неравенств

	n	1	n
	xi		xin (k 1, 2, ..., n).
	i 1	n 1 i 1
	i k		i k

Из соотношения (1.2) с учетом последних неравенств будем иметь

n	n			n				n		n
(n 1) xin		xk xin 1					xk(n 1) xi
i 1	k 1		i 1					k 1		i 1
			i k							i k
		n		n					n
	(n 1)			x		(n 1)n x .
		k 1	i 1		i				i 1	i
	n			n
Следовательно, xin		n xi, что и требовалось доказать.
	i 1			i 1

1.4.2. Историческая справка

Впервые метод математической индукции для получения строгих доказательств был применен в 1575 г. итальянским уче- ным Франческо Мауролико. В начале XVII в. Пьер Ферма усовершенствовал этот метод. Ферма называл его «методом бесконечного спуска». В середине XVII в. метод математической индукции подробно рассматривается в работах Блеза Паскаля, которому, вероятно, принадлежит наибольший вклад в развитие этого метода. Выражение «математическая индукция» было, по видимому, введено А. де Морганом в начале XIX в. Нельзя сказать, что это название особо удачное, поскольку появляется опасность спутать метод математической индукции с тем, что в

41