17 октября 2008 года.

...Чтобы продать что-нибудь ненужное надо сначала купить что-нибудь ненужное...

Э. Успенский

Листок 3. Математическая индукция.

Иногда приходится доказывать утверждения такого типа: "Для любого целого n ⩾ p выполнено ...". Доказательство таких утверждений базируется на аксиоме индукции. Пусть для некоторого утверждения A доказаны две теоремы: Теорема 1. Утверждение A справедливо при n = p. Теорема 2. Из того, что утверждение A верно при p ⩽ n ⩽ k, следует, что оно верно и при n = k + 1. Тогда в качестве аксиомы (она называется аксиомой индукции) принимается, что утверждение A верно для всех n ⩾ p (n, p, k — целые числа). Метод доказательств, основанный на аксиоме индукции называется методом математической индукции (ММИ).

1. Докажите, что для любого натурального n:

а) S_{n} = 1 + 2 + 3 + … + n = \frac{n(n + 1)}{2}; б) S_{n}^{2} = 1^{2} + 2^{2} + 3^{2} + … + n^{2} = \frac{n(n + 1)(2n + 1)}{6};

в) S_{n}^{3} = 1^{3} + 2^{3} + 3^{3} + … + n^{3} = \frac{n^{2}(n + 1)^{2}}{4} ;

2. Докажите, что для любого натурального n:

а) (1 − \frac{1}{4}) (1 − \frac{1}{9}) … (1 − \frac{1}{n^{2}} ) = \frac{n + 1}{2n};  б) n (2n^{2} − 3n + 1) ··· 6;  в) 7^{n+1} + 8^{2n−1} ··· 19;
г*) 11^{n+1} + 12^{2n−1} ··· 133;  д*) \underbrace{111 … 1}_{243 единицы} ··· 243;  е*) \underbrace{111 … 1}_{n} \underbrace{555 … 5}_{n−1} 6 — полный квадрат.

3. Докажите неравенство: \frac{1}{1^{2}} + \frac{1}{2^{2}} + … + \frac{1}{n^{2}} < 2. \underline{Указание.} Воспользуйтесь тем, что \frac{1}{(n − 1)n} = \frac{1}{n − 1} − \frac{1}{n}.

4. На плоскости провели несколько прямых. Докажите, что части, на которые рассечена плоскость, можно раскрасить в два цвета так, что соседние части (те, которые имеют оющий отрезок прямой) были раскрашены в разные цвета.

5. Докажите, что через n точек, не все из которых лежат на одной прямой, можно провести хотя бы n прямых.

6. а) На плоскости проведено n прямых, причем каждые две пересекаются, и никакие три не проходят через одну точку. Найдите число частей, на которые они разбивают плоскость.

б) На плоскости проведено n окружностей, причем любые две пересекаются в двух точках, и никакие три не проходят через одну точку. Найдите число частей, на которые они разбивают плоскость.

7. В компании из k ⩾ 4 человек каждый знает новость, которая больше никому неизвестна. За один телефонный разговор двое могут сообщить друг другу все известные им новости. Докажите, что достаточно 2k − 4 разговора, чтобы каждый человек узнал все новости.

8. Пусть x + \frac{1}{x} — целое. Докажите, что x^{n} + \frac{1}{x^{n}} — тоже целое.

9! Докажите Неравенство Бернулли: (1 + x)^{n} ⩾ 1 + xn, где x ⩾ −1, n ∈ ℕ.

\underline{Примечание.} Эта задача является обязательной.

10. а) Докажите, что 2^{k} > k при любом k ∈ ℕ; б*) Докажите, что 2^{k} > k^{n} при любом n ∈ ℕ, k ∈ ℕ, k ⩾ N (N зависит от n);

\underline{Указание.} Попробуйте найти N.

в*) Докажите, что α^{k} > k^{n} при любом α > 1, n ∈ ℕ, k ∈ ℕ, k ⩾ N (N зависит от n). 11*. Докажите, что при любом натуральном n ⩾ 6 справедливо неравенство 2^{n}n! < n^{n}.

12. Догадайтесь, чему равны следующие суммы и докажите правильность своей догадки :)

а) 1 + 3 + 5 + … + (2n − 1);  б) 1 + 2 + 4 + … + 2^{n};  в) 1^{2} + 3^{2} + 5^{2} + … + (2n − 1)^{2};
г) 1+3+9+…+3^{n};  д) \frac{1}{3} + \frac{1}{8} + \frac{1}{15} +…+ \frac{1}{n^{2} − 1};  е) 2^{n} +2^{n−1} ·3+2^{n−2} ·3^{2} +…+2·3^{n−1} +3^{n}.

Сдать до 27 октября.