Делимость

[Руст]

Заданы натуральные числа а и b, большие 1 и рекурентно определяется последовательность:
$x_0=0,x_1=1, \ x_{2k}=ax_{2k-1}-x_{2k-2}, \ x_{2k+1}=bx_{2k}-x_{2k-1}.$
Доказать, что для любых натуральных n и m имеет место:
$x_1x_2...x_m|x_{n+1}x_{n+2}...x_{n+m}.$

[Sasha2]

Интересно, а что означает вертикальная черта между этими двумя произведениями?

[незваный гость]

$a|b$ читается как $a$ делит $b$ (нацело). Т.е. $a|b \Leftrightarrow b \, \vdots \, a$.

[Sasha2]

ёПока не могу найти решения, но мне снова кажется
1) в обоих случаях мы вычитаем из одного члена последовательности тот, который остоит от него на два по номеру.
2) А теперь надо попытаться записать единой формулой уменьшаемое, типа 1+(-1) в какой то степени умноженное на a и то же самое для b

[maxal]

Нетрудно получить другую рекуррентную формулу:

$$x_{k+2} = (ab-2) x_{k} - x_{k-2}$$

Откуда, в частности, можно получить явные формулы, делимость $x_k | x_t$ при $k|t$ и свойство $НОК(x_p,x_q)=x_{НОК(p,q)}$ (по аналогии с числами Фибоначчи).

Ну а далее требуемое свойство делимости следует из того, что число $\frac{(n+1)\cdot(n+2)\cdot \dots\cdot (n+m)}{1\cdot 2\cdot\dots\cdot m}={n+m\choose n}$ является целым.

[Руст]

maxal писал(а):

Нетрудно получить другую рекуррентную формулу:

$$x_{k+2} = (ab-2) x_{k} - x_{k-2}$$

Откуда, в частности, можно получить явные формулы, делимость $x_k | x_t$ при $k|t$ и свойство $НОК(x_p,x_q)=x_{НОК(p,q)}$ (по аналогии с числами Фибоначчи).

Как получаются отсюда свойства делимости. Даже я не понял. Изложите для форумчан поконкретнее.

[maxal]

Для примера такое доказательство свойства $(x_p,x_q)=x_{(p,q)}$.

Во-первых, индукцией по $n$ доказываем формулу

$$a x_{k+2n} = x_{2n+2} x_k - x_{2n} x_{k-2}.$$

Во-вторых,
$(x_{k+2},x_k)=((ab-2)x_k-x_{k-2},x_k)=(x_k,x_{k-2})=\dots$ $=(x_2,x_0)=a$ для четного $k$ и $=(x_3,x_1)=1$ для нечетного $k$.

Теперь для чисел одной четности $p<q$ положим $n=(q-p)/2$ . Тогда

$$a x_q = x_{2n+2} x_p - x_{2n} x_{p-2}$$

и поэтому $(x_q,x_p)=(x_{q-p}, x_p)$ (учитывая что для четных $k$, $x_k$ делится на $a$, а для нечетных - не делится).
Отсюда следует, что $(x_q,x_p)=x_{(q,p)}$.

Пусть теперь $p$ - нечетное число. Тогда

$$a x_{2p+1} = x_{p+3} x_p - x_{p+1} x_{p-2}$$

и

$$ a x_{2p+1} = a(b x_{2p} - x_{2p-1}) = ab x_{2p} - x_{p+1} x_p + x_{p-1} x_{p-2}$$

.
Поэтому

$$ab x_{2p} = (x_{p+3} + x_{p+1}) x_p - (x_{p+1} + x_{p-1}) x_{p-2} = a x_{p+2} x_p + a x_p x_{p-2}$$

откуда $b x_{2p} = (x_{p+2} - x_{p-2}) x_p = ((ab-2) x_p - 2x_{p-2}) x_p$.
Нетрудно увидеть, что скобка делится на $b$, а поэтому $x_p\mid x_{2p}$.

Пусть $p$ и $k$ - нечетные числа. Тогда

$$(a x_{kp},x_{2p})= (x_{(k-1)p+2} x_p - x_{(k-1)p} x_{p-2},x_{2p})=(x_{(k-1)p+2} x_p,x_{2p}).$$

Учитывая, что $(x_{(k-1)p+2},x_{2p})=x_2=a,$ получаем $(x_{kp},x_{2p})=x_p.$

Наконец, пусть $p$ и $q$ числа разной четности, а именно $p$ - нечетное, $q$ - четное. Пусть $d=(p,q)$ и $k=p/(p,q)$. По доказанному имеем
$(x_{2p}, x_q) = x_{2d},$
$(x_p,x_q) = (x_p,x_{2p},x_q) = (x_p, x_{2d}) = (x_{kd}, x_{2d}) = x_d.$

[Руст]

Вообще то всё это мне кажется несколько проще получит из явного представления решения через сумму степеней алгебраических чисел. В принципе и там из-за отличия формул для чётных и нечётных членов, придётся разбирать эти случаи отдельно.