ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60601
Темы:    [ Цепные (непрерывные) дроби ]
[ Линейные рекуррентные соотношения ]
[ Индукция (прочее) ]
[ НОД и НОК. Взаимная простота ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

  Пусть a0 – целое, a1, ..., an – натуральные числа. Определим две последовательности
P–1 = 1,  P0 = a0,  Pk = akPk–1 + Pk–2  (1 ≤ k ≤ n);   Q–1 = 0,  Q0 = 1,  Qk = akQk–1 + Qk–2  (1 ≤ k ≤ n).
  Дроби Pk/Qk называются подходящими дробями к числу  [a0; a1, a2, ..., an].
  Докажите, что построенные последовательности для k = 0, 1, ..., n обладают следующими свойствами:
    а)  Pk/Qk = [a0; a1, a2,..., ak];
    б)  PkQk–1Pk–1Qk = (–1)k+1;
    в)   (Pk, Qk) = 1.


Решение

  а) Индукция. База. При  k = 0, 1  равенство проверяется непосредственно.
  Шаг индукции. Подходящая дробь с номером  k + 1  получается из k-й дроби заменой ak на   ak + :  [a0; a1, ..., ak, ak+1] = [a0; a1, ..., ak + ].
  Делая такую замену в равенстве     приходим к соотношению
[a0; a1, ..., ak, ak+1] = = .

  б) Легко проверяется по индукции.

  в) Из б) немедленно следует, что числа Pk и Qk взаимно просты.

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 3
Название Алгоритм Евклида и основная теорема арифметики
Тема Алгебра и арифметика
параграф
Номер 5
Название Цепные дроби
Тема Цепные (непрерывные) дроби
задача
Номер 03.149

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .