Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
34.18. Оба утверждения непосредственно следуют из задачи. Дело в том, что если равенство (3) выполняется при всех вещественных x, y, x 6= y, то f “ x + y 2 ” = f (x) Чтобы доказать это, заменим в (3) x на x + y, а y на x − y. В результате получим + y) − g(x − при всех вещественных x, y, y 6= 0. Положив в (4) x = u + и x = u − v, получаем+ v + y) − g(u + v − y) = 2y f (u + v), f(u − v + y) − g(u − v − y) = 2y f (u − Заменим теперь в (4) x на u, а y сначала на v − y, а потом на y − v: f(u + v + y) − g(u − v − y) = 2(v + y) f (u), f(u − v + y) − g(u + v − y) = −2(v − Сравнивая сумму этих двух уравнений с суммой предыдущих уравнений, получаем f (u + v) + f (u − v) = Положив u + v = x, u − v = y, получим требуемое равенство f (x) + f (y) = 2 f “ x + y 2 ” Глава 34. Функциональные уравнения. а) Если a = 1 и f(x) = a 0 x n + a 1 x n −1 + . . . + a n , где a 0 6= то получаем тождество a 0 x n + a 1 x n −1 + . . . + a n = a 0 (x + b ) n + a 1 (x + b ) n −1 + . . . + Такое тождество возможно лишь в том случае, когда a 1 = a 1 + те Если a = −1, то уравнение f(−x + b ) = f(x) после замены f(x + b /2) сводится к уравнению g(x) = g(−x), решениями которого служат многочлены вида+ a 2 x 2n−2 + . . . + б) При произвольном сравнение коэффициентов при старшем члене многочлена f(x) = a 0 x n + . . . показывает, что a n = 1. 34.21. Достаточно рассмотреть многочлены вида f(x) = x n + + a 1 x n −1 + . . . + a n . Требуется доказать, что a j = C j n b j ( a − при 1, . . . , n − 1. Доказательство проведём индукцией по Сравнение коэффициентов при для многочленов и f( a x + b ) показывает, что (1 − a n −j )a j = j −1 X s =0 a s C j −s n −s a n −j b j −s (1) При j = 1 получаем (1 − a n −1 )a 1 = C 1 n a n −1 b . По условию a n = поэтому C 1 n a −1 b 1 − a −1 = C 1 n b a − База индукции доказана. Для доказательства шага индукции (те. перехода от j = к j = k + 1) мы снова воспользуемся соотношением (1) и условием a n = 1. По предположению индукции a s = C s n b s ( a − при s=1, . . . , k. Поэтому (1 − a n −k−1 )a k +1 =C k +1 n a n −k−1 b k +1 + k X s =1 C s n C k +1−s n −s a n −k+1 b k +1 ( a −1) s Легко проверить, что C s n C k +1−s n −s = C k +1 n C s k +1 . Поэтому C k +1 n a n −k−1 b k +1 h 1 + C 1 k +1 1 a − 1 + . . . + C k k +1 1 ( a − 1) k i Решения задач 483 Ясно также, что выражение в квадратных скобках равно + 1 a − 1 ” k +1 − “ 1 a − 1 ” k +1 = a k +1 − 1 ( a − Следовательно 1 − a n −k−1 C k +1 n b k +1 a n − a n −k−1 ( a − Учитывая, что a n = 1, получаем C k +1 n b k +1 ( a − 1) k +1 ГЛАВА ЦЕПНЫЕ ДРОБИ. Определение и основные свойства Рассмотрим бесконечную последовательность натуральных чисел. Пусть a 0 — целое число и a 1 ]=a 0 + 1 a 1 = a 0 a 1 + 1 a 1 = p 1 q 1 , [a 0 ; a 1 , a 2 ]=a 0 + 1 a 1 + 1 a 2 = a 0 a 1 a 2 + a 0 + a 2 a 1 a 2 + 1 = p 2 q 2 , [a 0 ; a 1 , a 2 , и т. д. Дробь p k /q k называют подходящей дробью порядка для рассматриваемой последовательности, а предел lim k →∞ p k /q k = = [a 0 ; a 1 , a 2 , . . .] называют цепной дробью*. Каждому положительному числу можно сопоставить его разложение в цепную дробь, те. последовательность чисел, a 1 , . . . , для которой [a 0 ; a 1 , a 2 , . . .] = a . А именно, a 0 = [ a ], a 1 = h 1 a − a 0 i , a 2 = 2 4 1 1 a − a 0 − a 1 3 5 , a 3 = 2 6 6 4 1 1 1 a − a 0 − a 1 − a 2 3 7 и т. д Такое название пришло из немецкого языка (Kettenbr¨uchen). Иногда используется название непрерывные дроби, которое пришло из английского языка (continued fractions). Условия задач. Докажите, что цепная дробь [0; 1, 1, 1, . . .] равна отношению меньшего отрезка к большему в золотом сечении, а цепная дробь [1; 1, 1, 1, . . .] — отношению большего отрезка к меньшему. Докажите, что цепные дроби связаны с алгоритмом Евклида следующим образом. Пусть m < n — два натуральных числа. Применим к ним алгоритм Евклида a 0 m + r 1 , m = a 1 r 1 + r 2 , r 1 = a 2 r 2 + r 3 , . . ., r s −1 = a s r s . Пусть [0; a k , a k+1 , . . . , a s ] для k = 0, 1, . . . , s. Тогда x 0 = m n , x 1 = r 1 m , x 2 = r 2 r 1 , . . ., x s = r s r s −1 35.3. Пусть p 0 = и q 0 = а) Докажите, что при k > 2 выполняются соотношения a k p k −1 + и q k = a k q k −1 + б) Докажите, что p k −1 q k − q k −1 p k = в) Докажите, что p k −2 q k − q k −2 p k = (−1) k −1 a k 35.4. Докажите, что последовательность сходится. Решите в натуральных числах уравнение − [0; 2, 3, 4, . . . , n] = [0; x 1 , x 2 , . . . , x n ]. 35.6. Докажите, что a 0 + 1 q 0 q 1 − 1 q 1 q 2 + 1 q 2 q 3 − . . . Рассмотрим последовательность многочленов K 0 = 1, K 1 (x 1 ) = x 1 , K n (x 1 , . . . , x n ) = x n K n −1 (x 1 , . . . , x n −1 ) + K n −2 (x 1 , . . . , Согласно задаче 35.3 a) получаем p n = K n +1 (a 0 , . . . , a n ) и q n = = K n (a 1 , . . . , a n ), те. Докажите, что K n (x 1 , . . . , x n ) представляет собой сумму всех мономов, которые получаются из x 1 x 2 . . . вы- чёркиванием нескольких непересекающихся пар соседних переменных x i x i+1 . При этом можно как ничего не вычёр- кивать, таки вычёркивать всё; в последнем случае считаем, что остаётся моном 1 (Эйлер Глава 35. Цепные дроби. Докажите, что другое рекуррентное соотношение, . . . , x n ) = x 1 K n −1 (x 2 , . . . , x n ) + K n −2 (x 3 , . . . , приводит к той же самой последовательности многочленов. Докажите, что количество мономов в K n (x 1 , . . . , равно числу Фибоначчи F n+1 35.2. Наилучшие приближения Пусть a — положительное число, x и y — целые неотрицательные числа, причём y > 1. Дробь x/y называют наилучшим приближением числа a , если для любой другой дроби a/b с меньшим знаменателем выполняется неравенство |a − b a | > |x − y a |. 35.10. Докажите, что наилучшими приближениями числа являются подходящие дроби разложения в цепную дробь и только они. Цепные дроби и уравнение Пелля Здесь мы обсудим ещё один подход к построению решений уравнения Пелля, основанный на разложении числа в цепную дробь. Пусть d — натуральное число, свободное от квадратов. Тогда все решения уравнения x 2 − dy 2 = ±1 в натуральных числах находятся среди подходящих дробей разложения числа в цепную дробь. Теперь нужно выяснить, какие именно подходящие дроби соответствуют решениям уравнения x 2 − dy 2 = Пусть и a ′ — корни одного итого же неприводимого квадратного трёхчлена, те и сопряжённые числа (см. с. Квадратичную иррациональность a называют приведённой, если a > 1 и −1 < a ′ < 0, те. Например, квадратичная иррациональность [ √ d ] + √ d приведённая. 35.12. Докажите, что цепная дробь приведённой квадратичной иррациональности чисто периодическая, те. она имеет вид [a 0 ; a 1 , . . . , a k , a 0 , a 1 , . . . , a k , . . .]. Решения задач. Пусть [a 0 ; a 1 , . . . , a k −1 , 2a 0 , a 1 , . . .], те. число делится на период. Докажите, что тогда подходящая дробь дат решение уравнения x 2 − dy 2 = Решения. Пусть x = [0; 1, 1, 1, . . .]. Тогда x = 1 1 + x , те Ясно также, что x > 0. Решая квадратное уравнение и отбрасывая отрицательный корень, получаем требуемое. Пусть y = [1; 1, 1, 1, . . .]. Тогда y − 1 = 1/y, те Ясно также, что y > 0. Решая квадратное уравнение и отбрасывая отрицательный корень, получаем y = √ 5 + 1 2 = 1 x 35.2. Рассмотрим последовательность чисел y 0 = m n , y 1 = r 1 m , y 2 = r 2 r 1 , . . . , y s = r s r s −1 . Каждое из этих чисел заключено между и 1. Легко проверить, что при k 6 s полагаем 0). Действительно, это равенство эквивалентно равенству r k a k + нужно положить m = и n = r −1 ). Следовательно [0; a s ], y s −1 = [0; a s −a , a s ], . . . , y 0 = [0; a 0 , . . . , a s ], что и требовалось. а) Применим индукцию по k. При k = 2 требуемые соотношения легко проверяются. Если a 0 , a 1 , . . . рассматривать как независимые переменные, то имеет место очевидное равенство a 1 , . . . , a k +1 ] = h a 0 ; a 1 , . . . , Поэтому согласно предположению индукции) + p k −1 a k +1 (a k q k −1 + q k −2 ) + б) ив) легко следуют из а. По построению разложения в цепную дробь a > a 0 , a 6 6 a 0 + 1 a 1 , и вообще, a > p 2k /q 2k и a 6 p 2k+1 /q 2k+1 . Кроме того Глава 35. Цепные дроби согласно задаче 35.3 в) p k −2 q k −2 − p k q k = ( −1) k −1 a k q k q k −2 Поэтому (для иррационального a ) p 0 q 0 < p 2 q 2 < . . . < a < . . . Теперь сходимость последовательности вытекает из того, что согласно задаче 35.3 б и q k → ∞ при k → ∞. 35.5. Ответ. Выражение в левой части больше 1/2, поэтому x 1 < 2, а значит, x 1 = Пусть [0; 3, 4, . . . , n] = a и [0; x 2 , . . . , x n ] = x. Тогда 1 − 1 2 + a = 1 1 + те. Таким образом, [1; 3, 4, . . . , n] = [x 2 ; x 3 , . . . , Ясно, что целые части выражений в левой и правой части равны и x 2 , поэтому x 2 =1. После этого получаем равенство [3; 4, . . . , n]= = [x 3 ; x 4 , . . . , x n ]. Снова сравнивая целые части, получаем x 3 = и т. д. Равенство из задачи 35.3 б) можно переписать в виде. Затем запишем p k −1 q k −1 = p k −2 q k −2 + ( −1) k −2 q k −2 q k −1 и т. д. до p 1 q 1 = p 0 q 0 + 1 q 0 q 1 = a 0 + 1 q 0 q 1 35.7. Применим индукцию по n. При n = 1 утверждение очевидно. Шаг индукции делается следующим образом. Мономы, которые получаются при вычёркивании нескольких пар x i x i +1 , можно разбить на две группы те, в которых переменная не вычеркнута, и те, в которых переменная вычеркнута. Поскольку вместе с обязательно вычёркивается x n −1 , это разбиение согласуется с рекуррентным соотношением. Те же самые рассуждения, что ив задаче 35.7, лишь с заменой на x 1 , показывают, что новая последовательность многочленов характеризуется с помощью вычёркиваний точно также, как и старая. Пусть a n = K n (1, 1, . . . , 1). Тогда a 0 = 1, a 1 = 1 и a n = a n −1 + + при n > 2. 35.10. Предположим сначала, что x/y — наилучшее приближение числа a = [a 0 ; a 1 , a 2 , . . .], которое не совпадает ни с одной Решения задач 489 подходящей дробью p n /q n . Покажем, что тогда p 0 /q 0 < x/y < Действительно, если x/y < p 0 /q 0 = a 0 , то 6 a − a 0 < a − x y 6 y “ a − x y ” = a y − Поэтому |x− a y | >| a −a 0 |, чего не может быть. А если x/y >p 1 /q 1 > > a , то 6 x y − p 1 q 1 поэтому > ˛ ˛ ˛ x y − p 1 q 1 ˛ ˛ ˛ а значит − a y | чего тоже не может быть. Из того, что точка x/y лежит внутри отрезка [p 0 /q 0 , следует, что она лежит между точками и по предположению она не совпадает ни с одной из них. Таким образом, при нечётном n p n −1 q n −1 < x y < p n +1 q n +1 прич тном n все неравенства заменяются на противоположные). Поэтому получаем неравенства 6 ˛ ˛ ˛ x y − p n −1 q n −1 ˛ ˛ ˛ < ˛ ˛ ˛ p n q n − p n −1 q n −1 ˛ ˛ ˛ = 1 q n q n −1 , 1 yq n +1 6 ˛ ˛ ˛ p n +1 q n +1 − x y ˛ ˛ ˛ 6 ˛ ˛ ˛ a − x y ˛ ˛ ˛, ˛ ˛ ˛ a − p n q n ˛ ˛ ˛ 6 ˛ ˛ ˛ p n q n − a ˛ ˛ ˛ + ˛ ˛ ˛ a − p n +1 q n +1 ˛ ˛ ˛ = ˛ ˛ ˛ p n q n − p n +1 q n +1 ˛ ˛ ˛ Значит, q n < y и − a y | > 1 q n +1 > |p n − a q n |. Это противоречит тому, что x/y — наилучшее приближение числа Предположим теперь, что x/y = p n /q n . Требуется доказать, что если a/b 6= и 1 6 b < q n , то q n a | 6 |a − Из равенств + ˛ ˛ ˛ p n −1 q n −1 − a ˛ ˛ ˛ = ˛ ˛ ˛ p n q n − p n −1 q n −1 ˛ ˛ ˛ = 1 q n q n −1 Глава 35. Цепные дроби и − ˛ ˛ ˛ p n +1 q n +1 − a ˛ ˛ ˛ = ˛ ˛ ˛ p n −1 q n −1 − p n +1 q n +1 ˛ ˛ ˛ следуют неравенства 6 |p n −1 − q n −1 a | 6 и равенство q n −1 a | + q n −1 |p n − q n a | = Если a = и b = q n −1 , то согласно (2) |p n − q n a | 6 1 q n +1 6 |p n −1 − q n −1 a | = |a − Поэтому будем считать, что |aq n −1 − bp n −1 | > 1. Тогда + ˛ ˛ ˛ a − p n −1 q n −1 − ˛ ˛ ˛ > ˛ ˛ ˛a − p n −1 q n −1 − ˛ ˛ ˛ те Поскольку b < q n , из равенства (3) следует неравенство q n −1 a | + q n −1 |p n − q n a | 6 Из неравенств (5) и (4) получаем |p n − q n a | 6 |a − b a |, что и требовалось. Согласно задаче 35.10 достаточно проверить, что если dy 2 = ±1, где x и y — натуральные числа, то x/y — наилучшее приближение числа случай y = 1 легко разбирается отдельно). Для начала заметим, что = 1 y ˛ ˛ ˛ x 2 − y 2 d x + y p d ˛ ˛ ˛ = 1 y(x + Кроме того, x 2 =dy 2 ±1>(d−1)y 2 , поэтому x+y √ d>( √ d −1+ √ d)y> > 2y при d > 2. Следовательно, |x − y √ d | < 1 Пусть a/b 6= x/y и |a − b √ d | 6 |x − y √ d | (a — целое число, b — натуральное число. Тогда 6 ˛ ˛ ˛ √ d − a b ˛ ˛ ˛ + ˛ ˛ ˛ √ d − x y ˛ ˛ ˛ < 1 2by + 1 2y 2 = y + Поэтому 2y < y + b, те. Это означает, что x/y — наилучшее приближение числа Решения задач. Число является корнем квадратного уравнения ax 2 + + bx + c = 0, где a, b, c — целые числа, поэтому a = −b ± p b 2 − 4ac 2a = = P ± √ D Q . Изменив при необходимости знак числа Q = 2a, можно считать, что a = P Пусть a = [a 0 ; a 1 , a 2 , . . .]. Рассмотрим остаточный член a k = = [a k ; a k +1 , a k +2 , . . .]; при этом a = [a 0 ; a 1 , . . . , Шаг. Остаточные члены принимают лишь конечное число различных значений. В частности, a k = a l для некоторых различных k и Из равенства a = P следует, что a ′ = P − √ D Q . Поэтому и 2P Q = a + a ′ > 0. Значит, Q > 0 и P > 0. По условию a ′ < 0 и a > 1, поэтому P и Q < P + √ D < 2 √ D. Таким образом, при фиксированном D существует лишь конечное число приведённых квадратичных ирраци- ональностей вида Покажем, что a 1 — приведённая квадратичная иррациональность вида. Неравенство a 1 > 1 следует непосредственно из определения. Из соотношения следует, что поэтому − 1 a ′ 1 = a 0 − a ′ > 1. Далее a 0 = P + √ D Q − где P 1 = a 0 Q −P. Напомним, что P=−b, Q=2a и D=b 2 −4ac. Поэтому число P 2 1 − D = a 2 0 Q 2 + 2a 0 Q + 4ac делится на Q. Следовательно − Q(P 1 + √ D) P 2 1 − Индукция по k показывает, что a k — приведённая квадратичная иррациональность вида, где P k , Q k — целые числа, поскольку a k = a k + 1 a k +1 . Мы уже показали, что количество при- ведённых квадратичных иррациональностей такого вида конечно. Ш а г 2. Если и k, l > 1, то a k −1 = a l −1 Глава 35. Цепные дроби Достаточно проверить, что если и a 1 — приведённые квадратичные иррациональности, связанные соотношением вида a = = a 0 + a −1 1 , где a 0 — натуральное число, то число однозначно восстанавливается по a 1 . Ясно, что и 0 < − a ′ < 1. Поэтому. Число однозначно восстанавливается по поэтому число тоже восстанавливается. Рассмотрим число a = [ √ d ] + √ d = [2a 0 ; a 1 , . . . , a k −1 , a ] = ˆ p k −1 a + ˆ p k −2 ˆ q k −1 a + где+ a 0 . Это число удовлетворяет квадратному уравнению С другой стороны a 0 + √ d, поэтому a 2 − 2a 0 a + (a 2 0 − d) = Следовательно, ˆp k −1 − ˆq k −2 = и ˆp k −2 = (d − a 2 Соотношение ˆp k −2 ˆ q k −1 − ˆq k −2 ˆ p k −1 = можно переписать в виде (d − a 2 0 )q 2 k −1 − ˆp k −1 (ˆ p k −1 − 2a 0 q k −1 ) = = (d − a 2 0 )q 2 k −1 − (p k −1 + a 0 q k −1 )(p k −1 − a 0 q k −1 ) = dq 2 k −1 − p 2 k −1 ГЛАВА ФОРМАЛЬНЫЕ РЯДЫ |