Уравнение Пелля и подходящие дроби.

[julyk]

Проверить, что ровно одна из двух соседних подходящих дробей к $\sqrt{3}$ дает решение уравнения $x^2 - 3y^2 = 1$.
Разложим $\sqrt{3}$ в подходящую дробь. Получим $[1,${1,2}$]$. Составим отношение:
$\frac{P_{k}}{Q_{k}} = \frac{a_{k}P_{k-1} + P_{k-2}}{a_{k}Q_{k-1} + Q_{k-2}}$.
Запишем базу:
$P_{0}^{2} - 3Q_{0}^{2} = 1 - 3 = -2$;
$P_{1}^{2} - 3Q_{1}^{2} = 4 - 3 = 1$;
$P_{2}^{2} - 3Q_{2}^{2} = 25-27 = -2$;
$P_{3}^{2} - 3Q_{3}^{2} = 49-48 = 1$.

Предположение:
$P_{2k-1}^2 - 3Q_{2k-1}^2= 1$;
$P_{2k-2}^2 - 3Q_{2k-2}^2= -2$.

Должно выполнятся равенство:

$$P_{2k+1}^{2} - 3Q_{2k+1}^{2}= 1.$$

$$(a_{2k+1}P_{2k} + P_{2k-1})^2 - 3(a_{2k+1}Q_{2k} + Q_{2k-1})^2 = 1.$$

Дальше надо как-то раскрыть, что-то сократить...это у меня и не получается. Преподаватель еще предложила "спуститься на индексы". Я не понимаю, как это сделать. Подскажите, пожалуйста.

[Sonic86]

Для доказательства нужно привлечь простые свойства $P_k,Q_k$ (раз уж Вы начали с ними оперировать). Какие их свойства Вы знаете?

(про формулы)

$\{a;b\}$

[julyk]

1. Для соседних подходящих дробей справедливо: $P_{k}Q_{k-1} - P_{k-1}Q_{k} = (-1)^{k-1}.$
2. Для подходящих дробей $\frac{P_{k-2}}{Q_{k-2}}$, $\frac{P_{k}}{Q_{k}}$ при $k>2$ справедливо:
$P_{k}Q_{k-2} - P_{k-2}Q{k} = (-1)^k\cdotb_1b_2...b_{k-1}a_{k}.$
3. Если $\frac{P_k}{Q_k}$, $\frac{P_{k+1}}{Q_{k+1}}$ - подходящие дроби для числа $\alpha$ , заданного обыкновенной непрерывной дробью, то выполняется неравенство:
$|{\alpha - \frac{P_k}{Q_k}}|\le \frac{1}{Q_{k}Q_{k+1}}.$

-- 02.01.2014, 17:39 --

P.S. С формулами косячу, т.к. давно в TeXe не работала).

[Sonic86]

Замечательно, Вам понадобится свойство 1 и ее рекуррентные соотношения

$$\left\{\begin{array}{ll} P_{k}=a_kP_{k-1}+P_{k-2} \\ Q_{k}=a_kQ_{k-1}+Q_{k-2} \end{array}$$

julyk в сообщении #808676 писал(а):

$$(a_{2k+1}P_{2k} + P_{2k-1})^2 - 3(a_{2k+1}Q_{2k} + Q_{2k-1})^2 = 1.$$

Дальше надо как-то раскрыть, что-то сократить...это у меня и не получается.

Подставьте явное выражение для $a_{2k+1}$, раскройте скобки, сгруппируйте, упростите немного как-нибудь, заюзайте свойства, напишите, что получилось.
Пробуйте, короче.

Доказательство будет отдельное для четных индексов, отдельное - для нечетных

[julyk]

Так, ну вот, собственно, мои попытки.
$(a_{2k+1}P_{2k})^2 - 3(a_{2k+1}Q_{2k}+Q_{2k-1})^2 = 1.$
Рассмотрим для $k=1,$ $k$-нечетное. $a_{2k+1}=1.$
Раскрываем скобки:
$P_{2k}^2 + 2P_{2k}P_{2k-1} + P_{2k-1}^2 - 3Q_{2k}^2 - 6Q_{2k}Q_{2k-1}-3Q_{2k-1}^2=1.$
Группируем:
$P_{2k}^2 - 3Q_{2k}^2 + 2P_{2k}{2k-1} - 6Q_{2k}Q_{2k-1} + P_{2k-1}^2 - 3Q_{2k-1}^2 = 1.$
Известно, что $P_{2k-1}^2 - 3Q_{2k-1}^2 = 1.$
$P_{2k}^2 - 3Q_{2k}^2 + 2(P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1})=0.$
Используя соотношения $P_{2k}=a_{2k}P_{2k-1}+P_{2k-2};$ $Q_{2k}=a_{2k}Q_{2k-1}+Q_{2k-2};$ запишем:
$(a_{2k}P_{2k-1}+P_{2k-2})^2 - 3(a_{2k}Q_{2k-1}+Q_{2k-2})^2 + 2(P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1})=0.$
$a_{2k}=2.$

$$4P_{2k-1}^2 + 4P_{2k-1}P_{2k-2}+ P_{2k-2}^2 - 12Q_{2k-1}^2 - 6Q_{2k-1}Q_{2k-2}-3Q_{2k-2}^2 + 2P_{2k}P_{2k-1} - 6Q_{2k}Q_{2k-1} = 0.$$

$$4 - 2 +4P_{2k-1}P_{2k-2} - 6Q_{2k-1}Q_{2k-2} + 2P_{2k}P_{2k-1} -6Q_{2k}Q_{2k-1} = 0.$$

$$2 + 2(2P_{2k-1}P_{2k-2} - 3Q_{2k-1}Q_{2k-2}) + 2(P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1}) = 0.$$

Вот, что получилось. Реккурентные соотношения я использовала, а свойство 1 - нет. Пока не знаю, как решать дальше. Может здесь есть ошибки?

[Sonic86]

julyk в сообщении #808754 писал(а):

Группируем:
$P_{2k}^2 - 3Q_{2k}^2 + 2P_{2k}{2k-1} - 6Q_{2k}Q_{2k-1} + P_{2k-1}^2 - 3Q_{2k-1}^2 = 1.$

$(P_{2k}^2 - 3Q_{2k}^2) + 2(P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1}) + (P_{2k-1}^2 - 3Q_{2k-1}^2) = 1$
Вам по предположению индукции известны 1-я и 3-я скобка. Что остается и чему это равно?

[julyk]

Так, получается:

$$-2 + 2P_{2k}P_{2k-1} - 6Q_{2k}Q_{2k-1} + 1 = 1.$$

$$2P_{2k}P_{2k-1} - 6Q_{2k}Q_{2k-1} = 2.$$

$$2(P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1}) = 2.$$

$$P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1} = 1.$$

[Sonic86]

Осталось добавить аргументов и разобрать случай с другой четностью индексов.

[julyk]

А что значит добавить аргументов?
Начинаю рассматривать второй случай. Возьмем $k=2,$ $a_{2k+1}$ = 1.
Предположение:
$P_{2k-1}^2 - 3Q_{2k-1}^2 = 49 - 3\cdot16 = 1;$
$P_{2k-2}^2 - 3Q_{2k-2}^2 = 25 - 3\cdot9 = -2.$

$P_{2k}^2 - 3Q_{2k}^2$ должно равняться $-2.$
$-2 + 2P_{2k}P_{2k-1} - 6Q_{2k}Q_{2k-1} + 1 = 1; $
$P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1} = 1.$

Получилось аналогично...как добавить аргументы?

[Sonic86]

julyk в сообщении #808783 писал(а):

А что значит добавить аргументов?

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

[julyk]

А, в смысле, добавить аргументы для доказательства. Я думала, в само выражение что-то надо добавить. Ну, я так понимаю, мы, например, во втором случае пишем предположение:

$$P_{2k-1}^2 - 3Q_{2k-1}^2 =1;$$

$$P_{2k-2}^2 - 3Q_{2k-2}^2 = -2.$$

И дальше, предполагаем, что выполняется и для следующей четной подходящей дроби, то есть, $P_{2k}^2 - 3Q_{2k}^2 = 2.$ И получаем равенство: $P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1} = 1.$ Вроде верно?
А почему эти действия доказывают??? Не могу понять

[Sonic86]

julyk в сообщении #808838 писал(а):

А почему эти действия доказывают??? Не могу понять

Давайте добьем первый случай, про второй пока забудем.
Соберем все в кучу.
Мы проводим индукционный шаг. Индукционные предположения у нас есть:
$P_{2k-1}^2 - 3Q_{2k-1}^2= 1$;
$P_{2k-2}^2 - 3Q_{2k-2}^2= -2$.
Есть также свойства, верные для всех $k$:
$P_{k}Q_{k-1} - P_{k-1}Q_{k} = (-1)^{k-1}.$
$\left\{\begin{array}{ll} P_{k}=a_kP_{k-1}+P_{k-2} \\ Q_{k}=a_kQ_{k-1}+Q_{k-2} \end{array}$
И нам надо доказать, что
$(a_{2k+1}P_{2k} + P_{2k-1})^2 - 3(a_{2k+1}Q_{2k} + Q_{2k-1})^2 = 1.$
Как это сделать?
Мы преобразуем последнее выражение равносильными преобразованиями. Значит получаем равносильное утверждение
$(P_{2k}^2 - 3Q_{2k}^2) + 2(P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1}) + (P_{2k-1}^2 - 3Q_{2k-1}^2) = 1$
Т.е. можно доказывать его вместо утверждения $(2P_{2k} + P_{2k-1})^2 - 3(2Q_{2k} + Q_{2k-1})^2 = 1$. Можем ли мы его доказать исходя из того, что есть? Как? Доведите рассуждение до конца явно.

[julyk]

Так как второе уравнение было получено равносильными преобразованиями, то мы можем его доказывать вместо первого. Подставляем значения из индукционных предположений и получаем, что

$$P_{2k}{2k-1} - 3Q_{2k}{2k-1} = 1.$$

И вот тут вопрос, что мы собственно получили? Может выполнение свойства $P_{k}Q_{k-1} - P_{k-1}Q_{k} = (-1)^{k-1}?$

[Sonic86]

Ага, я тупанул Сам не проверил явно и Вам сижу говорю

Решение не проходит. Из общих соображений не следует, чему равно $P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1}$. То, что оно равно $1$ нужно доказывать отдельно. У меня пока просто не получилось (хотя я мог опять тупануть). М.б. индуктивное предположение "слабое".

Вообще, почему мы доказываем именно по индукции? Если по-другому не получится, то можно в лоб, топорно (я сейчас проверил - у меня получилось), но это в каком-то смысле грубо. Схема такая: составляем рекуррентное уравнение для $P_k,Q_k$, из них составляем рекуррентное уравнение для $P_{2k+1},Q_{2k+1}$, решаем его как обычное разностное уравнение, подбираем коэффициенты, аналогично получаем формулы и для $P_{2k},Q_{2k}$, подставляем и проверяем соотношения $P_{2k-1}^2 - 3Q_{2k-1}^2= 1$ и $P_{2k}^2 - 3Q_{2k}^2= -2$.
Но это грубо, хочется попробовать как-то поумнее, а я пока не понял как. Если по-другому не получится, будем так делать, как выше написал.

-- Сб янв 04, 2014 17:12:17 --

Sonic86 в сообщении #809524 писал(а):

Из общих соображений не следует, чему равно $P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1}$. То, что оно равно $1$ нужно доказывать отдельно. У меня пока просто не получилось (хотя я мог опять тупануть).

Почти так и есть: я тупанул Его вполне можно доказать вместе, по индукции, используя рекуррентные соотношения для $P_k, Q_k$ (в них есть вся информация) и индуктивные гипотезы.
Т.е. мы вместо одного соотношения должны доказывать сразу 4 и при доказательстве использовать все 4 тоже. Ну бывает...
Тоже (будет тоже 2 случая): сначала найдем значение $V_{k}=P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1}$ и $W_{k}=P_{2k-1}P_{2k-2} - 3Q_{2k-1}Q_{2k-2}$ при $k=1;2$. Делаем предположение о значении $V_k, W_k$. Затем с помощью рекуррентных формул и индуктивного предположения (из 1-го поста!) выражаем $V_k, W_k$ через $V_{k-1}, W_{k-1}$. Все, делаем вывод, а потом его юзаем для проведения индукции в рассуждении выше до конца. Попробуйте. Я тоже попробую...

[julyk]

Рассмотрим $V_{k}:$
при $k=1$ получим $P_{2}P_{1} - 3Q_{2}Q_{1} = 1;$
при $k=2$ получим $P_{4}P_{3} - 3Q_{4}Q_{3} = 1;$
Рассмотрим $W_{k}:$
при $k=1$ получим $P_{1}P_{0} - 3Q_{1}Q_{0} = -1;$
при $k=2$ получим $P_{3}P_{2} - 3Q_{3}Q_{2} = -1;$
Предположения:
$P_{2k}P_{2k-1} - 3Q_{2k}Q_{2k-1} = 1;$
$P_{2k-1}P_{2k-2} - 3Q_{2k-1}Q_{2k-2} = -1;$

$V_{k-1} = P_{2k-1}P_{2k-2} - 3Q_{2k-1}Q_{2k-2}$;
$W_{k-1} = P_{2k-2}P_{2k-3} - 3Q_{2k-2}Q_{2k-3}$;

Выразить пока не получилось...если я конечно правильно записала $V_{k-1}$ и $W_{k-1}.$