2014-06-07
Доказать, что для любого значения $n \in \mathbf{N}$ имеет место равенство
$\sum_{1 \leq i_{1} < i_{2} < \cdots < i_{k} \leq n} \frac{1}{i_{1}i_{2} \cdots i_{k}} =n$
где суммирование ведется по всем возможным наборам чисел
$ i_{1} < i_{2} < \cdots < i_{k}, k=l, 2, \cdots, n$,
из множества ${1; 2; ...; n}$.
Решение:
Первое решение. Рассмотрим многочлен
$P(x) = \left ( x + \frac{1}{1} \right ) \left ( x + \frac{1}{2} \right ) \cdots \left ( x + \frac{1}{n} \right )$,
который по теореме Виета имеет вид
$P(x) = x^{n}+a_{1}x^{n-1} + a_{2}x^{n-2} + \cdots + a_{n}$,
где обозначено
$a_{1} = \sum_{i_{1}=1 }^{n} \frac{1}{i_{1}}, a_{2}= \sum_{1 \leq i_{1} < i_{2} \leq n } \frac{1}{i_{1}i_{2}}, \cdots a_{n}= \frac{1}{1 \cdot 2 \cdots n}$,
Тогда указанная в условии задачи сумма равна
$a_{1}+a_{2}+ \cdots + a_{n} = P(1) – 1 = $
$= \left ( 1 + \frac{1}{1} \right ) \left ( 1 + \frac{1}{2} \right ) \cdots \left ( 1 + \frac{1}{n} \right ) – 1 = \frac{2 \cdot 3 \cdots (n+1)}{1 \cdot 2 \cdots n} -1 = (n+1) – 1 =n$,
что и требовалось доказать.
Второе решение. Обозначим
$\sum_{1 \leq i_{1} < \cdots < i_{k} \leq n} \frac{1}{i_{1} \cdots i_{k}}$
через $S_{n}$ и докажем индукцией по $n$, что $S_{n}=n$. При $n = 1$ это верно:
$S_{1}= 1$. Пусть $n \geq 2$ и $S_{n-1} = n – 1$, тогда
$S_{n}-S_{n-1}= \sum_{1 \leq i_{1} < \cdots < i_{k} = n} \frac{1}{i_{1} \cdots i_{k}}=$
$= \frac{1}{n} + \sum_{1 \leq i_{1} < \cdots < i_{l} \leq n-1} \frac{1}{i_{1} \cdots i_{l} \cdot n} = \frac{1}{n} + \frac{S_{n-1}}{n}$,
т. е.
$S_{n}=S_{n-1} + \frac{S_{n-1}}{n} + \frac{1}{n} = (n-1) + \frac{n-1}{n}+ \frac{1}{n}=n$