Условие
Определим последовательности чисел (xn) и
(dn) условиями x1 = 1, xn+1 = [ 
], dn = x2n+1 – 2x2n–1 (n ≥ 1).
Докажите, что число 
в двоичной системе счисления представляется в виде (d1,d2d3...)2.
Решение
1) Заметим, что 
при x ≥ 1 (оба неравенства проверяются возведением в квадрат).
2) Пусть a = , bn = {2n–1a}. Тогда bn – иррациональное число, bn+1 = {2bn}. В любом из этих случаев bn+1 – abn < 1 – a/2.
Кроме того, 
при n > 1: 22n–1 не является квадратом, но кратно 4, а [2n–1a]² ≡ 0 или 1 (mod 2), поэтому числитель не меньше 3.
3) Пусть yn = an–1 + an–2. Докажем по индукции, что xn = [yn].
База. x1 = 1 = [a0 + a–1] по условию, 
Шаг индукции. Предположим, xn = [yn].
Пусть n = 2m, тогда yn = 2m–1a + 2m–1, [yn+1] = 2m + 2m–1a, поэтому {yn} = {yn+1} = bm, 
С другой стороны, 
xn+1 + bm – abm + 3a/8 > [yn+1] – bm/2 + 3a/8 > yn+1 – ½ + 3a/8 > yn+1. Следовательно, 
Пусть n = 2m + 1 > 1, тогда yn = 2m + 2m–1a, yn+1 = 2ma + 2m, поэтому {yn} = bm, {yn+1} = {2bm},
xn+1 < a(xn + ½) = yn+1 – abm + a/2 = [yn+1] + bm+1 – abm + a/2 < [yn+1] + 1 – a/2 + a/2 = [yn+1] + 1.
Если bm < ½, то bm+1 = 2bm, 
Следовательно, xn+1 ≥ [yn+1].
Если bm > ½, то bm+1 = 2bm – 1. Кроме того, 1/8xn ≤ 1/2m+3.
Значит, 
[yn+1] + 2–a/2bm+1 – a/2 + a/2 – a/8xn ≥ [yn+1] + 3(2–a)/2m+2 – a/2m+3 > [yn+1]. Следовательно, xn+1 = [yn+1]. (Использовано доказанное в 2) неравенство bm+1 > 3/2m+1a = 3a/2m+2.)
4) Отсюда следует, что x2n+1 – 2x2n–1 = [2n + 2n–1a] – 2[2n–1 + 2n–2a] = [2n–1a] – [2n–2a], а это и есть (n–1)-й знак после запятой в двоичной записи числа a.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
Алфутова Н.Б., Устинов А.В. |
|
Год издания |
2002 |
|
Название |
Алгебра и теория чисел |
|
Издательство |
МЦНМО |
|
Издание |
1 |
|
глава |
|
Номер |
5 |
|
Название |
Числа, дроби, системы счисления |
|
Тема |
Системы счисления |
|
параграф |
|
Номер |
1 |
|
Название |
Рациональные и иррациональные числа |
|
Тема |
Дроби |
|
задача |
|
Номер |
05.037 |
