2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Делимость
Сообщение25.08.2006, 19:48 
Заслуженный участник


09/02/06
4382
Москва
Заданы натуральные числа а и 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}.$

 Профиль  
                  
 
 
Сообщение25.08.2006, 20:08 


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

 Профиль  
                  
 
 
Сообщение25.08.2006, 20:13 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
$a|b$ читается как $a$ делит $b$ (нацело). Т.е. $a|b \Leftrightarrow b \, \vdots \, a$.

 Профиль  
                  
 
 
Сообщение25.08.2006, 21:49 


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

 Профиль  
                  
 
 
Сообщение25.08.2006, 23:31 
Модератор
Аватара пользователя


11/01/06
5660
Нетрудно получить другую рекуррентную формулу:
$$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}$ является целым.

 Профиль  
                  
 
 
Сообщение26.08.2006, 08:03 
Заслуженный участник


09/02/06
4382
Москва
maxal писал(а):
Нетрудно получить другую рекуррентную формулу:
$$x_{k+2} = (ab-2) x_{k} - x_{k-2}$$
Откуда, в частности, можно получить явные формулы, делимость $x_k | x_t$ при $k|t$ и свойство $НОК(x_p,x_q)=x_{НОК(p,q)}$ (по аналогии с числами Фибоначчи).

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

 Профиль  
                  
 
 
Сообщение27.08.2006, 05:09 
Модератор
Аватара пользователя


11/01/06
5660
Для примера такое доказательство свойства $(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.$

 Профиль  
                  
 
 
Сообщение27.08.2006, 06:06 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group