Номер 2.46, страница 56 - гдз по алгебре 9 класс учебник Шыныбеков, Шыныбеков

2.46. Докажите тождество $(C_n^0)^2 + (C_n^1)^2 + \dots + (C_n^n)^2 = C_{2n}^n.$

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

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

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

С одной стороны, общее количество способов выбрать $n$ человек из $2n$ по определению равно биномиальному коэффициенту $C_{2n}^n$. Это правая часть нашего тождества.

С другой стороны, представим, что группа из $2n$ человек состоит из двух подгрупп: $n$ мужчин и $n$ женщин. Комитет из $n$ человек можно сформировать, выбрав $k$ женщин из $n$ и, соответственно, $n-k$ мужчин из $n$. Здесь $k$ — это количество женщин в комитете, которое может меняться от $0$ до $n$.

Количество способов выбрать $k$ женщин из $n$ равно $C_n^k$.

Количество способов выбрать $n-k$ мужчин из $n$ равно $C_n^{n-k}$.

Для каждого конкретного $k$ количество способов сформировать комитет с $k$ женщинами и $n-k$ мужчинами равно произведению $C_n^k \cdot C_n^{n-k}$.

Чтобы найти общее число способов сформировать комитет, нужно просуммировать эти произведения по всем возможным значениям $k$ от $0$ до $n$:$$ \text{Общее число способов} = \sum_{k=0}^{n} C_n^k \cdot C_n^{n-k} $$

Эта сумма имеет вид: $C_n^0 C_n^n + C_n^1 C_n^{n-1} + \dots + C_n^n C_n^0$.

Используем свойство симметрии биномиальных коэффициентов: $C_n^j = C_n^{n-j}$. Применяя это свойство, мы видим, что $C_n^{n-k} = C_n^k$. Таким образом, каждый член суммы $C_n^k \cdot C_n^{n-k}$ можно переписать как $C_n^k \cdot C_n^k = (C_n^k)^2$.

Тогда вся сумма преобразуется в:$$ \sum_{k=0}^{n} (C_n^k)^2 = (C_n^0)^2 + (C_n^1)^2 + \dots + (C_n^n)^2 $$

Это выражение является левой частью доказываемого тождества. Поскольку мы считали одно и то же (общее количество способов сформировать комитет) двумя разными методами, полученные выражения должны быть равны. Следовательно:$$ (C_n^0)^2 + (C_n^1)^2 + \dots + (C_n^n)^2 = C_{2n}^n $$Что и требовалось доказать.

Способ 2: Алгебраический

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

Рассмотрим биномиальное разложение:$$ (1+x)^n = \sum_{k=0}^{n} C_n^k x^k = C_n^0 + C_n^1 x + C_n^2 x^2 + \dots + C_n^n x^n $$

Воспользуемся очевидным тождеством: $(1+x)^{2n} = (1+x)^n \cdot (1+x)^n$.

С одной стороны, коэффициент при $x^n$ в разложении $(1+x)^{2n}$ по формуле бинома Ньютона равен $C_{2n}^n$. Это правая часть нашего тождества.

С другой стороны, найдем коэффициент при $x^n$ в произведении двух одинаковых разложений:$$ (C_n^0 + C_n^1 x + \dots + C_n^n x^n) \cdot (C_n^0 + C_n^1 x + \dots + C_n^n x^n) $$

При перемножении этих двух многочленов член, содержащий $x^n$, образуется путем суммирования произведений членов вида $(C_n^k x^k)$ из первого многочлена и $(C_n^{n-k} x^{n-k})$ из второго, где $k$ пробегает все возможные значения от $0$ до $n$. Коэффициент при $x^n$ будет равен сумме коэффициентов этих произведений:$$ \text{Коэффициент при } x^n = \sum_{k=0}^{n} C_n^k \cdot C_n^{n-k} $$

Используя свойство симметрии биномиальных коэффициентов, $C_n^{n-k} = C_n^k$, мы можем переписать каждый член суммы $C_n^k \cdot C_n^{n-k}$ как $C_n^k \cdot C_n^k = (C_n^k)^2$. Таким образом, вся сумма коэффициентов равна:$$ \sum_{k=0}^{n} (C_n^k)^2 = (C_n^0)^2 + (C_n^1)^2 + \dots + (C_n^n)^2 $$

Это левая часть доказываемого тождества. Так как коэффициенты при одной и той же степени $x$ в левой и правой частях тождества $(1+x)^{2n} = (1+x)^n \cdot (1+x)^n$ должны быть равны, мы получаем:$$ (C_n^0)^2 + (C_n^1)^2 + \dots + (C_n^n)^2 = C_{2n}^n $$Что и требовалось доказать.

Ответ: Тождество $(C_n^0)^2 + (C_n^1)^2 + \dots + (C_n^n)^2 = C_{2n}^n$ доказано. Были представлены два метода доказательства: комбинаторный (через подсчет числа комбинаций двумя способами) и алгебраический (через сравнение коэффициентов при разложении бинома). Оба метода подтверждают справедливость тождества.