Суммы и произведения

31

Мы записьаем формулы, как правило, коротко, с помощью обозначений

$$\sum_{k=1}^{n} a_k = a_1 + a_2 + \dots + a_n,$$

$$\prod_{k=1}^{n} b_k = b_1 \cdot b_2 \cdot \dots \cdot b_n,$$

$$n! = 1 \cdot 2 \cdot \dots \cdot n.$$

Советуем тем, кто еще не научился ими пользоваться, расписывать выкладки более подробно.

1. Остаточная крайние

Этот заголовок обьясняется следующим очередным равенством:

$$(a_2 - a_1) + (a_3 - a_2) +$$

$$+ (a_4 - a_3) + \dots + (a_n - a_{n-1}) +$$

$$+ (a_{n+1} - a_n) = a_{n+1} - a_1$$

(1)

или

$$\sum_{k=1}^{n} (a_{k+1} - a_k) = a_{n+1} - a_1,$$

(1')

из которого можно, выбирая различным образом последовательность $(a_k)$, получить много отнюдь не оченьных равенств.

Пример 1. Положив $a_k = -\frac{1}{k}$, получаем $\sum_{k=1}^{n} \frac{1}{k(k+1)} = \frac{n}{n+1}$; трудно найти задачник по алгебре, где бы не встречался этот пример.

Пример 2. Положим $a_k = k(k-1)d/2$. Поскольку $a_{k+1} - a_k = kd$, равенство (1) принимает вид $\sum_{k=1}^{n} kd = (n+1) \cdot n \cdot d/2$. Добавив к каждому члену суммы следа еще по $a - d$, а к сумме справа $n(a - d)$, получаем известную формулу для суммы $n$ членов арифметической прогрессии: $a + (a + d) + \dots + (a + (n-1)d) = n(a - d) + (n+1)nd/2 = na + n(n-1)d/2$.

Упражнение 1. Возьмите в (1) $a_k = (2k-1)^3/24$ и получите формулу для $\sum_{k=1}^{n} k^2$.

32

Пример 3. Пусть $m$ – натуральное число. Положим $a_k = \frac{1}{(m+2)} \times (k-1)k(k+1) \dots (k+m)$. Тогда $a_{k+1} - a_k = \frac{1}{m+2}k \cdot (k+1) \dots (k+m) + 1 + m) - \frac{1}{m+2}(k-1)k \dots (k+m) = k(k+1) \dots (k+m)$. В этом случае равенство (1) записывается так:
$$\sum_{k=1}^{n} k(k+1) \dots (k+m) = \frac{1}{m+2}n(n+1) \dots (n+m+1).$$
Равенство (1) можно использовать и по-другому. Пусть нам надо доказать, что
$$\sum_{k=1}^{n} f(k) = g(n).$$
Попробуем доказать равенство
$$g(k) - g(k-1) = f(k).$$
Если нам это удался, то будет доказано и (2). В самом деле, рассмотрим вспомогательную последовательность
$$\left\{ \begin{array}{l} a_1 = 0, \\ a_{k+1} = g(k). \end{array} \right.$$
Для этой последовательности равенство (1) имеет вид
$$\sum_{k=1}^{n} [g(k) - g(k-1)] = g(n),$$
что, ввиду (3), равносильно (2).
Докажем, например, таким способ равенство
$$\sum_{k=1}^{n} C_{l+k-1}^{l+1} = C_{l+n}^{l+1}.$$
В соответствии со сказанным для этого достаточно проверить равенство $C_{l+n}^{l+1} - C_{l+n-1}^{l+1} = C_{l+n-1}^{l+1}$ или $C_{l+n-1}^{l+1} + C_{l+n-1}^{l+1} = C_{l+n}^{l+1}$, вытекающее из известного точекства $C_n^m + C_n^{m+1} = C_n^{m+1}$ («Алгебра и начала анализа 9», п. 8). В п. 3 мы доказем точекство (4) другим способом.
Все вышесказанное переносится и на произведение. Напишем, прежде всего, мультитипликатный аналог равенства (1):
$$\frac{a_2}{a_1} \cdot \frac{a_3}{a_2} \cdot \frac{a_4}{a_3} \dots \frac{a_n}{a_{n-1}} \cdot \frac{a_{n+1}}{a_n} = \frac{a_{n+1}}{a_1}$$
(*) Через $n!!$ обозначается произведение натуральных чисел от 1 до $n$, имеющих одинаковую четность с $n$. Например, $8!! = 2 \cdot 4 \cdot 6 \cdot 8, 9!! = 1 \cdot 3 \cdot 5 \cdot 7 \cdot 9$.

33

4. $$\sum_{k=1}^{n} k \cdot k! = (n+1)! - 1.$$

5. $$\prod_{k=1}^{n} k^k \cdot k! = (n!)^{n+1}.$$

6. $$a_1 + (a_1+1) a_2 + (a_1+1) (a_2+1) \times a + \ldots + (a_1+1) (a_2+1) \ldots (a_{n-1}+1) \times a_n = (a_1+1) (a_2+1) \ldots (a_n+1) - 1.$$

7. $$\sum_{k=1}^{n} \frac{1}{k(k+1) \ldots (k+m)} = \frac{1}{m} \left( \frac{1}{m!} - \frac{1}{(n+1)(n+2) \ldots (n+m)} \right).$$

8. $$\sum_{k=1}^{n} \frac{x^k \cdot k!}{(x+1)(2x+1) \ldots (kx+1)} = \frac{1}{x-1} \frac{x^{n+1}(n+1)!}{(x+1) \ldots (nx+1)} + \frac{x}{1-x}.$$

9. $$\sum_{k=0}^{n-1} \frac{p_0 \cdot p_1 \ldots p_k q_{k+1}}{(p_1+q_1) \ldots (p_{k+1}+q_{k+1})} = 1 - \frac{p_1 p_2 \ldots p_n}{(p_1+q_1) \ldots (p_n+q_n)}.$$
   (Здесь $(p_k)$ и $(q_k)$ – две последовательности и $p_0 = 1$.)
   К сожалению, указывающий способ годится только в том случае, когда в сумме $$\sum_{k=1}^{n} b_k$$ слагаемые $b_k$ не зависят от $n$. В следующем пункте мы будем доказывать равенства, в которых слагаемые зависят от $n$.

10. Метод «туда-назад»

Название этого метода (но не сам метод) – выдума автора. Историки математики утверждают, что именно с его помощью маленький Гауссудивил своего школьного учителья, быстро найдя сумму натуральных чисел от 1 до 100. Покажем применение метода «туда-назад» на примерах.

Докажем, что для нечетного $n$
$$\sum_{k=0}^{n} (-1)^k \sqrt{C_n^k} = 0.$$
Запишем сумму $S_n$ двумя способами
$$S_n = \sqrt{C_n^0} - \sqrt{C_n^1} + \sqrt{C_n^2} - \ldots + \sqrt{C_n^{n-1}} - \sqrt{C_n^n} \text{ (туда)},$$

$$S_n = -\sqrt{C_n^0} + \sqrt{C_n^1} + \ldots - \sqrt{C_n^n} + \sqrt{C_n^0} \text{ (назад)}$$

В нашей сумме перед $$\sqrt{C_n^n}$$ знак минус, потому что $n$ нечетно. Сложим два полученных выражения:

$$2S_n = \left( \sqrt{C_n^0} - \sqrt{C_n^n} \right) + \left( -\sqrt{C_n^1} + \sqrt{C_n^{n-1}} \right) + \ldots + \left( -\sqrt{C_n^n} + \sqrt{C_n^0} \right).$$

Легко сообщить, что в каждой скобке стоит нуль, так как $C_n^m = C_n^{n-m}$. Поэтому $2S_n = 0$, откуда $S_n = 0$.

Еще пример:

$$\sum_{k=0}^{2n+1} \frac{(-1)^k}{C_{2n+1}^k} = 0.$$

Действует аналогично:

$$S_n = \frac{1}{(C_{2n+1}^0)^2} - \frac{1}{(C_{2n+1}^1)^2} + \ldots - \frac{1}{(C_{2n+1}^n)^2} \text{ (туда)},$$

$$S_n = -\frac{1}{(C_{2n+1}^0)^2} + \frac{1}{(C_{2n+1}^1)^2} - \ldots + \frac{1}{(C_{2n+1}^n)^2} \text{ (назад)}$$

Складывая эти выражения и учтывая, что $C_{2n+1}^k = C_{2n+1}^{2n+1-k}$, получаем $2S_n = 0$. Отсюда $S_n = 0$.

А вот более сложный, но и более интересный пример на эту же тему:

$$\sum_{k=0}^{n} \frac{(-1)^k}{C_n^k} = \frac{n+1}{n+2} (1 + (-1)^n).$$

Решить эту задачу так же просто, как две предыдущие, не удаляя. Обозначим $$\sum_{k=0}^{n} \frac{(-1)^k}{C_n^k}$$ через $S_n$. Если $n$ нечетно, вы без труда доказете, что $S_n = 0$. Случай же четного $n$ сведем к нечетному. Проследите внимательно, как это делается.

34

Обозначим $\sum_{k=0}^{n} \frac{(-1)^k (k+1)}{C_n^k}$ через $T_n$.

Запишем $T_n$ двумя способами:

$$T_n = \frac{1}{C_n^0} - \frac{2}{C_n^1} + \dots + \frac{n+1}{C_n^n} \text{ (туда)},$$

$$T_n = \frac{n+1}{C_n^n} - \frac{n}{C_n^{n-1}} + \dots + \frac{1}{C_n^0} \text{ (назад)}.$$

Складывая, получаем $2T_n = (n+2) \times \left( \frac{1}{C_n^0} - \frac{1}{C_n^1} + \dots + \frac{1}{C_n^n} \right) = (n+2) \times S_n$. С другой стороны, $T_n = \sum_{k=0}^{n} \frac{(-1)^k (k+1) k! (n-k)!}{n!} = (n+1) \sum_{k=0}^{n} \frac{(-1)^k}{C_n^{k+1}} = (n+1) (1 - S_{n+1})$.

Но так как $S_{n+1} = 0$ ($n+1$ нечетно), $T_n = n+1$. Мы уже доказали, что $S_n = \frac{2}{n+2} T_n$. Значит, $S_n = \frac{2(n+1)}{(n+2)}$.

Осталось заметить, что $\frac{n+1}{n+2} (1 + (-1)^n) = \left\{ \begin{array}{l} 0, n нечетно, \\ \frac{2(n+1)}{n+2}, n четно. \end{array} \right.$

Доказательство равенства

$$\sum_{k=0}^{n} \frac{1}{C_n^k} = \frac{n+1}{2^{n+1}} \sum_{k=1}^{n+1} \frac{2^k}{k}. \tag{9}$$

сложнее всех предыдуших, но оно и само поучительное.

Введем следующие обозначения:

$$\sum_{k=0}^{n} \frac{1}{C_n^k} = D_n; \quad \sum_{k=0}^{n} \frac{k+1}{C_n^k} = E_n;$$

$$\frac{n+1}{2^{n+1}} \sum_{k=1}^{n+1} \frac{2^k}{k} = F_n.$$

Сначала по методу «туда-назад» дважды запишем сумму

$$E_n = \frac{1}{C_n^0} + \frac{2}{C_n^1} + \dots + \frac{n+1}{C_n^n} \text{ (туда)},$$

$$E_n = \frac{n+1}{C_n^n} + \frac{n}{C_n^{n-1}} + \dots + \frac{1}{C_n^0} \text{ (назад)}.$$

Сложим эти равенства: $2E_n = (n+2) \times \sum_{k=0}^{n} \frac{1}{C_n^k} = (n+2) D_n$. Значит, $D_n = \sum_{k=0}^{n} \frac{1}{C_n^k} = (n+2) E_n$. Теперь, продолжав выкладки, аналогичные тем, которые мы провели при решении предыдушей задачи, выразим $E_n$ через $D_{n+1}$.

А именно, $E_n = \sum_{k=0}^{n} \frac{k+1}{C_n^k} = (n+1) \times \sum_{k=0}^{n} \frac{1}{C_n^{k+1}} = (n+1) (D_{n+1} - 1)$, и мы можем выразить $D_{n+1}$ через $D_n$:

$$D_{n+1} = \frac{2}{n+2} E_n = \frac{2}{n+2} (n+1) (D_{n+1} - 1),$$

откуда

$$D_{n+1} = 1 + \frac{n+2}{2(n+1)} D_n.$$

Теперь, пользователь математической индукции, доказем, что $D_n = F_n$ при всех целых $n \geqslant 0$. Легко видеть, что $D_0 = 1$ и $F_0 = 1$. Предположим, что $D_s = F_s$. Тогда $D_{s+1} = 1 + \frac{s+2}{2(s+1)} D_s = 1 + \frac{s+2}{2(s+1)} F_s = 1 + \frac{s+2}{2(s+1)} \cdot \frac{s+1}{2^{s+1}} \sum_{k=1}^{s+1} \frac{2^k}{k} = 1 + \frac{s+2}{2^{s+1}} \sum_{k=1}^{s+1} \frac{2^k}{k} = F_{s+1}$.

Значит, $D_n = F_n$ при всех целых $n \geqslant 0$. Задча решения.

Доказав равенства (8) и (9), мы решили задачу М470 («Квант», 1977, № 10). Равенство (9) позволяет предложить новое решение задачи М434 («Квант», 1977, № 12).

Пусть $\sum_{k=1}^{n} \frac{2^k}{k} = \frac{p_n}{q_n}$, где $p_n, q_n$ взaimно просты. Обозначим через $v(n)$ наиболееую степень числа 2, на которой делится $p_n$. Доказем, что $v(n) \geqslant \frac{n-3}{2}$.

Из (9) $\sum_{k=0}^{n} \frac{1}{C_n^k} = \frac{n+1}{2^{n+1}} \frac{p_{n+1}}{q_{n+1}}$. По-этому $\frac{p_{n+1}}{q_{n+1}} = \frac{2^{n+1}}{n+1} \sum_{k=0}^{n} \frac{1}{C_n^k}$ или $\frac{p_n}{q_n} = \frac{2^{n}}{n} \sum_{k=0}^{n-1} \frac{1}{C_n^k}$. Отсюда $\frac{p_n}{q_n} = \frac{2^{n}}{n}! \times ((n-1)! + 1! (n-2)! + 2! (n-3)! + \dots + (n-1)!)$. В $n!$ число 2 входит в степень $\left[ \frac{n}{2} \right] + \dots \leqslant$

36

многочлен
$$f(x) = (1+x)^n (x+1)^n = \left( C_n^0 + C_n^1 x + C_n^2 x^2 + \dots + C_n^n x^n \right) \times \left( C_n^0 x^n + C_n^1 x^{n-1} + C_n^2 x^{n-2} + \dots + C_n^n \right).$$

Коэффициент при $x^n$ в этом произведении равен, очевидно, $\sum_{k=0}^{n} \left( C_n^k \right)^2$.

С другой стороны, $f(x) = (1+x)^2n$. Коэффициент при $x^n$ в нем равен $C_{2n}^n$. По теореме получаем, что $\sum_{k=0}^{n} \left( C_n^k \right)^2 = C_{2n}^n$.

Тепер найдем $\sum_{k=0}^{n} (-1)^k \left( C_n^k \right)^2$.

При решении предыдущего задачи мы рассматривали многочлен $f(x) = (1+x)^n (x+1)^n$. Здесь же, по-видимому, надо взять положий многочлен, но чтобы в нем знаки у коэффициентов через линейные. Давайте попробуем рассмотреть многочлен $g(x) = (1+x)^n (x-1)^n = \left( C_n^0 + C_n^1 x + \dots + C_n^n x^n \right) \left( C_n^0 x^n - C_n^1 x^{n-1} + \dots + (-1)^n C_n^n \right)$.

Коэффициент при $x^n$ в этом произведении равен $\sum_{k=0}^{n} (-1)^k \left( C_n^k \right)^2$. С другой стороны, $g(x) = (1+x)^n (x-1)^n = (-1)^n (1-x^2)^n = (-1)^n \times \sum_{k=0}^{n} (-1)^k C_n^k x^{2k}$. В этой сумме коэффициенты при нечетных степенях $x$ равны 0. Поэтому, если $n$ нечетно, то коэффициент при $x^n$ равен 0. Если же $n$ четно, то коэффициент при $x^n$ равен $(-1)^{n+\frac{n}{2}} C_n^{\frac{n}{2}} = (-1)^{\frac{n}{2}} C_n^{\frac{n}{2}}$. Итак, $\sum_{k=0}^{n} (-1)^k \left( C_n^k \right)^2 = \left\{ \begin{array}{l} 0, n \text{ нечетно}, \\ (-1)^{\frac{n}{2}} C_n^{\frac{n}{2}}, n \text{ четно}. \end{array} \right.$

Уражнения

14. Найдите сумму $\sum_{k=0}^{n} \frac{C_n^k}{k+1}$. (Ответ: $\frac{2^{n+1}-1}{n+1}$.)

15. Обозначим через $B_n^k$ коэффициент при $x^k$ в многочлен $(1+x+x^2)^n$. Найдите сумму $\sum_{k=0}^{2n} \left( B_n^k \right)^2$. (Ответ: $B_{2n}^n$).

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

Тем не менее мы думаем, что, решив предложенные упражнения, вы можете самостоятельно решать аналогичные задачи.

4. Преобразование Абеля

Пусть нам дана сумма $S_n = a_1 b_1 + a_2 b_2 + \dots + a_n b_n$, где $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ – две последовательности. Обозначим суммы $b_1, b_1 + b_2, \dots, b_1 + b_2, \dots, b_1 + b_2 + \dots + b_n$, соответствующего, через $B_1, B_2, \dots, B_n$. Тогда $b_1 = B_1, b_k = B_k - B_{k-1}$ при $k > 1$ и $\sum_{k=1}^{n} a_k b_k$ можно преобразовать так:

$$\sum_{k=1}^{n} a_k b_k = a_1 B_1 + a_2 (B_2 - B_1) + \dots + a_n (B_n - B_{n-1}) = (a_1 - a_2) B_1 + (a_2 - a_3) B_2 + \dots + (a_{n-1} - a_n) B_{n-1} + a_n B_n = \sum_{k=1}^{n-1} (a_k - a_{k+1}) B_k + a_n B_n.$$

Это преобразование называют преобразование Абеля (о замечательном порядке математике Нильссе Хенрике Абелле см. в «Кванте» № 5 за 1976 год).

Воспользовавшись преобразованиями Абеля, найдем сумму $\sum_{k=1}^{n} kq^{k-1}$.

Положим в точкестве (10) $a_1 = 1, a_2 = 2, \dots, a_n = n; b_1 = 1, b_2 = q, \dots, b_n = q^{n-1}$. Тогда $B_k = \frac{q^k - 1}{q-1}$ и $a_1 - a_2 = a_2 - a_3 = \dots = a_{n-1} - a_n = -1$. Позотому

$$\sum_{k=1}^{n} kq^{k-1} = \sum_{k=1}^{n-1} (-1) \frac{q^k - 1}{q-1} +$$