Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
G (х) не как Функцию аргумента х, а просто как некоторый формальный
объект (аналогично многочлены в сущности тоже можно рассматривать как
формальные объекты, которые не следует путать с функциями). Термин
"производящая функция" был перенесен сюда со случая последовательностей
действительных или комплексных чисел, где может оказаться, что ряд,
аналогичный (tm)-13), сходится при подстановке некоторого действительного
Нли комплексного числа jt0 вместо переменной х, что позволяет приписать
какое-то конкретное значение функции G (х"). В рассматриваемой же
ситуации вопрос о сходимости или расходимости
0*
516
Гл. 8. Линейные рекуррентные последовательности
ряда (8.13) не возникает, так как мы рассматриваем G (х) "иероглиф"
последовательности s0, 51? ... .
В общем случае выражение вида
$>.
/
\
&
90
В (X) = bv Ьхх ~f Ъгх% +.
|- Ьпхп +
Е ьахп>
п= О
А;
где Ь0, ... - последовательность элементов из fqi
называ
формальным, степенным рядом (над полем f9). В таком тексте члены blh Ьг,
... нашей последовательности называют-также коэффициентами формального
степенного ряда. Прила тельное "формальный" вновь отражает ту мысль, что
сходим или расходимость этих выражений (какой бы смысл мы в это
вкладывали) не имеет никакого отношения к их изучению, j формальных
степениых ряда над
оо
00
В{х)
Л Ьпхп и С (х)
л~0
Е Спхп
О
считаются равными, если Ьп = сп для всех п -- О, 1, ... . Тай образом,
множество всех формальных степенных рядов иад находится во взаимно
однозначном соответствии с множест всех последовательностей, состоящих нз
элементов поля Может показаться, что мы ничего не выиграем от перехода к
мальным степенным рядам. На самом деле "смысл существоваад! этих объектов
состоит в том, что мы можем наделить множес формальных степенных рядов
над F$ богатой и интересной гебраической структурой, причем совершенно
естественным об зом. Это будет обсуждаться впоследствии.
Заметим, во-первых, что многочлен
Р(х) = Рь ~г PiX -Г
PhXk ? Fn [х]
¦ .ф
тоже можно рассматривать как формальный степенной ряд # отождествляя его
с рядом
Р (*) = Ро -г PlX
pkxk -j- 0 • xk +1 -f- 0 • хк +2 +
<
;Ъ:
1
Введем теперь алгебраические операции сложения и умиожей формальных
степенных рядов таким образом, чтобы они являл перенесением на множество
формальных степенных рядов с ветствующих операций, определенных на
многочленах. Под нее, если
оо
В (х)
? Ьп*п л ^0
И
С (х)
s
п - О
спхп
§ 3. Производящие функции
517
два формальных степенных ряда над F#, то определим их сумму как
формальный степенной ряд
00
В (х) 4- С (х) = 2 (Ьп + сп) хп, а их произведение - как формальный
степенной ряд
00 п
В (х)С(х) ~ 2 dnxnt где dn = 2 я = О, 1, ... .
"-О k^Q
Если В (х) и С (х) оба являются многочленами над F"f то определенные выше
операции совпадают со сложением н умножением обычных многочленов. Здесь
же надо отметить, что принцип подстановки, который так полезен в алгебре
многочленов, не действителен для формальных степенных рядов по той
простой причине, что выражение В (а), где а - элемент поля Г9, а ^ (дг) -
формальный степенной ряд над может быть бессмысленным. Это плата за то,
что мы игнорируем вопросы сходимости рядов.
8.35. Пример. Пусть
00
В (х) - 2 -f х2 и С (х) = 1 4- х +х2 -f ' * ' + хП • " 2j * * х*
п-О
- формальные степенные ряды иад полем Fa* Тогда
00
В (х) 4 С (х) - х + 2х2 -f х3 -f ** *' + х" + * ' * ~ Е dnxnt
п -О
где - 0, d1 - 1, - 2 и 4 = * Ддя всех я > 3, а
В (х) С (х) = 2 + 2х + 0*х3 -Е 0*х3 + ... - 2 + 2х. ?
Очевидно, что сложение формальных степенных рядов над F^
является ассоциативной и коммутативной операцией. Формаль-
00
ный степенной ряд 0 - 2 (r)'хП является нулем относительно
00
операции сложения. Если В (х) = 2 ^пхП - произвольный фор-
п~ О
мальный степенной ряд надр^" то обратным к нему относительно
00
операции сложения является степенной ряд 2 (-&n) xtl> который
я-О
обозначается через -В (х). Обычно мы будем писать В (х) - С (х) вместо В
(х) + (-С (х)).
Очевидно, что и операция умножения формальных степенных Рядов над Fff
является коммутативной операцией, а формальный
518
Гл. 8. Линейные рекуррентные последовательности
bVi
•:"д
степенной ряд 1 = 1 | О-х + О х2 + ••¦ + 0*хп + ... - един: ный элемент
относительно операции умножения. Умноже: является ассоциативной
операцией, так как если
•• пй
оо
оо
оо
В (х) -= J] Ьпхп, С (х) - 2 спхп> D(x)= 2 dnxn,
"=0 "=0 п= 0
щ
;vki
Ч-.1
то оба формальных степенных ряда
(В (х) С (х)) D (х) и В (х) (С (X) D (х))
равняются
00
? ( ? biCjdk\x",
n~l0 \<ь /. А ) 6 L ("> /
где L (я) - множество всех упорядоченных троек (i, /, k), / ^ О, k О, I
д- / + k - rt. Кроме того, справедлив д и стр иб у ти в ноет и
оо
л
В (х) (С (X) + D (X)) = 2 I ? Ь* f d"_*)) X" =
"=0 \fe~0
00
/1
n-0 \fe=0
, ,\Y
1 A
xKJ
s
Щ
"l Л
к - Ц*
•'*3
4
vl
.ж
3aici
,a5
¦?
J(r)
ii
it
№ s.'.
00
n
00
n
• i
S-Tf!
? ?M".xU-+s ? М-Д*"
ra -0 \ k=D
n -0 \ fe -0
