Об уравнении C_n^m = C_n+1^m-1

21

Об уравнения
$$C_n^m = C_{n+1}^{m-1}$$

А. Ширшов

К уравнению, указаноному в заглавии, я пришел, рассматривая 14-ю строку треугольника Паскала:
1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1.

О треугольнике Паскала рассылается в пунктах 7 и 8 учебного пособия «Алгебра и начала аналiza 9».

Коротко рассакjem о нем тем, кто с ним еще не знаком.

В n-й строке треугольника Паскала на m-m месте стоит число $C_n^m$, причем нумерация как строк, так и чисел в каждой строке начинается с нуля (первые 15 строк треугольника Паскала приведены на рисунке).

Для понимания статьи достаточно о числах $C_n^m$ знать только одно:
$$C_n^m = \frac{n!}{m!(n-m)!}$$

($n! = 1 \cdot 2 \cdot \dots \cdot n; 0! = 1$). Из (1) легко выводится
$$C_n^m + C_{n+1}^{m+1} = C_{n+1}^{m+1}.$$

С помощью этого соответствия можно строить треугольник Паскала, не пользоваться формулой (1) (см. рисунок).

В 14-й строке бросается в глаза, что 1001+2002=3003, то есть
$$C_{14}^4 + C_{14}^5 = C_{14}^6.$$

Ввиду (2) это равенство можно переписать так:
$$C_{15}^5 = C_{14}^6.$$

Равенство (3) показывает, что пара (6, 14) является решением уравнения, указаноного в заглавии.

А какие еще пары чисел являются решением этого уравнения? В статье дается ответ на этот вопрос. Чтобы ответ имел более красивую форму, заменим в нашем уравнения m на y, а n — на x—1. Тогда верна такая теорема. Все решения уравнения $C_x^{y-1} = C_x^{-1}$ имеют вид
$$x_k = \gamma_{2k} \gamma_{2k+1}; \quad y_k = \gamma_{2k-1} \gamma_{2k}, \quad k = 1, 2, 3, \dots, \text{еде } \gamma_n - n-\text{й член последовательности Фибоначчи}^*): 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$$

Доказательство.

1. Воспользовемся формулой (1) и перепишем наше уравнение:
   $$\frac{x!}{(y-1)!(x-y+1)!} = \frac{(x-1)!}{y!(x-y-1)!}.$$

После очевидных преобразований оно приводится к таким виду:
$$(x-y+1)(x-y)=xy.$$

Обозначим через w наиболее общий делитель чисел x и y. Тогда x=uw, y=vw, где u и v взаимно просты. Подставив выражения для x и y в (4), после сокращения на w получим, что $(u-v)[(u-v)w+1]=uvw.$

Числа u и v взаимно просты. Поэтому u-v и uv тоже взаимно просты. Взаимно просты и числа w и $(u-v)w+1$. Но тогда должны выполнять такие равенства:
$$\begin{cases} (u-v)w+1=uv, \\ u-v=w. \end{cases}$$

*) Для этой последовательности $\gamma_n = \gamma_{n-1} + \gamma_{n-2}$ для n > 2.

22

Эта система равnocильна такой системе:

$$\begin{cases} v^2 + vw - w^2 = 1, \\ v + w = u. \end{cases}$$

Поэтому решение нашего уравнения совпадается к решению уравнения

$$v^2 + vw - w^2 = 1$$

в натуральных числах.

2. Сделаем три простых замена о решении уравнения (7). Пусть пара $\langle v, w \rangle$ является решением уравнения (7). Тогда

a) $v$ и $w$ взаимно просты;
b) если $v = w$, то $v = w = 1$;
c) $v \leq w < 2v$;
d) пары $\langle v + w, v + 2w \rangle$ и $\langle 2v - w, w - v \rangle$ являются решением уравнения.

Напомним, что $v$ и $w$ — натуральные числа.

в) вытекает из равенства $w = \frac{v + \sqrt{5v^2 - 4}}{2}$, получающегося, если (7) рассмотреть как уравнение относительно $w$, а г) можно проверить, подставив соответствующие пары в уравнение (7).

С помощью преобразования

$$\langle v, w \rangle \Rightarrow \langle v + w, v + 2w \rangle,$$

исходя из решения $\langle 1, 1 \rangle$, построим последовательность решений $\langle 2, 3 \rangle, \langle 5, 8 \rangle, \langle 13, 21 \rangle, \langle 34, 55 \rangle, \dots$.

ВЫПисанные решения имеют вид

$$v_h = \gamma_{2h-1}, w_h = \gamma_{2h}.$$

Докажем, что других решений уравнения (7) не имеет. Допустим, что пара $\langle v, w \rangle$ является решением уравнения (7). Докажем, что она является одной из пар (8).