Номер 34.17, страница 280 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 6. Элементы комбинаторики и теории вероятностей. Параграф 34. Метод математической индукции - номер 34.17, страница 280.

Условие.

34.17. Докажите, что количество всех подмножеств данного $n$-элементного множества равно $2^n$.

Решение.

Данное утверждение можно доказать несколькими способами. Приведём два из них.

Способ 1: Комбинаторный

Пусть дано множество $S$, состоящее из $n$ элементов: $S = \{a_1, a_2, \dots, a_n\}$. Каждое подмножество этого множества формируется путем принятия решения для каждого элемента: включать его в подмножество или не включать. Рассмотрим каждый элемент по очереди:

• Для элемента $a_1$ существует 2 варианта: он либо принадлежит подмножеству, либо не принадлежит.
• Для элемента $a_2$ также существует 2 варианта.
• ...
• Для элемента $a_n$ также существует 2 варианта.

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

$$ \underbrace{2 \times 2 \times \dots \times 2}_{n \text{ множителей}} = 2^n $$

Это можно также представить как количество всех двоичных строк длины $n$, где каждая позиция в строке соответствует элементу множества, а значение (0 или 1) указывает на его отсутствие или присутствие в подмножестве. Количество таких строк равно $2^n$. Что и требовалось доказать.

Способ 2: С использованием биномиальных коэффициентов

Общее количество подмножеств $n$-элементного множества можно найти, сложив количества подмножеств всех возможных размеров. Размер подмножества $k$ может принимать любое целое значение от $0$ (пустое множество) до $n$ (само исходное множество).

Количество способов выбрать $k$ элементов из $n$ (то есть количество подмножеств размера $k$) равно биномиальному коэффициенту $C_n^k$ или $\binom{n}{k}$.

Чтобы найти общее количество всех подмножеств, нужно просуммировать их количества для всех возможных размеров $k$ от $0$ до $n$:

$$ N = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} $$

Эта сумма является частным случаем формулы бинома Ньютона:

$$ (x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k $$

Если в эту формулу подставить $x=1$ и $y=1$, то получим:

$$ (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k $$

$$ 2^n = \sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} $$

Таким образом, общее количество подмножеств $N$ равно $2^n$. Что и требовалось доказать.

Ответ: Утверждение доказано. Количество всех подмножеств данного $n$-элементного множества равно $2^n$.