Сборник задач по математике с решениями для поступающих в вузы

Метод доказательства, основанный на использовании аксиомы индукции, называется методом математической индукции.

С помощью метода математической индукции можно доказать формулы

20.1. Докажите неравенство

20.2. В арифметической прогрессии а₁, а₂, ..., а_n первый член равен разности прогрессии: а₁ = d. Считая число n данным, найдите

20.3. Найдите сумму

20.4. Найдите зависимость между натуральными n и А, если

где а /= 0, 1, -1.

20.5. Найдите коэффициент при хⁿ в разложении

(1 + x + 2х^2 + ... + пхⁿ)^2.

20.6. Решите неравенство

|x - 2х^2 + 4х^3 - 8х

⁴ + ... + (-2)ⁿ - 1хⁿ + ...| 1.

20.7. Найдите сумму

S_n = 1 · 1! + 2 · 2! + 3 · 3! + ... + n · n!.

20.8. Найдите сумму

S_n = x + 4х^3 + 7х⁵ + 10х⁷ + ... + (3n - 2)х²ⁿ - 1.

20.9. Найдите сумму

S_n⁴  = 1⁴ + 2⁴ + 3⁴ + ... + n⁴,

считая известными формулы для S_n, S_n

^2, S_n^3 (см. с. 103).

20.10. Натуральные числа разбиты на группы

(1), (2, 4), (3, 5, 7), (6, 8, 10, 12), (9, 11, 13, 15, 17), ...

Найдите сумму чисел в n-й группе.

20.11. Вычислите выражение

20.12. Найдите сумму

1 + 2 · 2 + 3 · 2^2 + ... + 100 · 2⁹⁹.

20.13. Найдите сумму ряда

Глава 21

Соединения и бином

Эта глава содержит задачи по комбинаторике, а также задачи, связанные с возведением в степень двучлена ax + b. Выражение (ax + b) называют биномом Ньютона и рассматривают, как правило, его разложение в ряд по степеням x и коэффициенты этого разложения — они зависят от а и b — при различных степенях x.

Комбинаторика изучает всевозможные комбинации из элементов данного конечного множества. Простейшие из таких комбинаций: перестановки, размещения и сочетания.

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

P(n

) = 1 · 2 · 3 · ... · n = n! (1)

Символ n! (читается «эн факториал») обозначает произведение первых n чисел натурального ряда: 1! = 1, 2! = 2, 3! = 6, 4! = 24, ... . По определению 0! = 1.

Следующий вид комбинаций — размещения из n различных элементов, образующих множество, в группы по k различных элементов в каждой. При этом два размещения считают разными, если они отличаются либо элементами, либо порядком их расположения. Подобные ситуации возникают при размещении постояльцев в гостинице, зрителей в театральном зале, пассажиров в поезде. Число всех возможных размещений по k различных элементов в каждом размещении, формируемых из n различных элементов данного множества, обозначают А_n^k. Имеет место формула:

Сочетания из n элементов по k элементов — комбинации, составленные из данных n элементов и содержащие по k (k = n) элементов в каждой, отличающиеся одна от другой хотя бы одним элементом. С — число сочетаний из n по k:

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

Если задан алфавит из n различных букв и поставлена задача составить всевозможные слова по k букв в каждом, то речь идет о размещениях с повторениями. Обратите внимание на то обстоятельство, что слова могут быть любой длины, а потому нет необходимости в выполнении ограничения k = n. Слова aba

и baa считаются различными (входящие в них элементы образуют разные последовательности).

Число  всевозможных различных размещений с повторениями из n различных элементов по k элементов в каждом находится по формуле

Доказывается эта формула с помощью рекуррентного соотношения

которое устанавливается следующим рассуждением. Если первая буква в слове из k букв фиксирована, то в оставшиеся k - 1 ячеек можно разметить буквы  способами. Для каждого из этих способов остается n возможностей для выбора буквы, стоящей на первом месте. В результате мы получим все размещения с повторениями из n по k.

Размещения с повторениями, образованные из n элементов a₁, a₂, ..., а_n так, что каждый из этих элементов входит в размещение по крайней мере один раз, называются перестановками с повторениями. Если известно, что элемент a₁ входит ₁ раз, элемент a₂ входит ₂ раз, ..., элемент a_n входит _n раз, то число всевозможных таких перестановок обозначают  и оно может быть найдено по формуле

Два сочетания с повторениями из n элементов по k в каждом считаются различными тогда и только тогда, когда они отличаются по крайней мере одним элементом или какой-нибудь элемент входит в эти соединения различное число раз. Число всевозможных сочетаний с повторениями определяется по формуле

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

Для любого натурального n справедливы разложения