Составители:
Рубрика:
где β(n) — число единиц в двоичном представлении n. В частности,
β(n) > 1, α(n) 6 n −1, (5.69)
причем равенства достигаются тогда и только тогда, когда n есть
степень двойки.
Д о к а з а т е л ь с т в о. Двоичное представление n соответ-
ствует записи
n = 2
n
1
+ 2
n
2
+ . . . + 2
n
k
,
где n
1
> n
2
> . . . > n
k
> 0, k = β(n) > 1. Представим n! в виде
n! = N
1
N
2
. . . N
k
,
где
N
1
= (2
n
1
)!, N
2
= (2
n
1
+ 1)(2
n
1
+ 2) . . . (2
n
1
+ 2
n
2
),
N
3
= (2
n
1
+ 2
n
2
+ 1)(2
n
1
+ 2
n
2
+ 2) . . . (2
n
1
+ 2
n
2
+ 2
n
3
), . . .
N
k
= (2
n
1
+ . . . + 2
n
k−1
+ 1)(2
n
1
+ . . . + 2
n
k−1
+ 2) . . . (2
n
1
+ . . . + 2
n
k
).
Разложение N
1
на простые множители содержит α(2
n
1
) двоек.
Разложение N
2
на простые множители содержит α(2
n
2
) двоек. Дей-
ствительно, входящий в N
2
общий множитель можно представить
в форме
2
n
1
+ 2
s
r = 2
s
(2
n
1
−s
+ r),
где r нечетно и 2
s
r < 2
n
1
. Поэтому слагаемое 2
n
1
не влияет на
результат. Аналогично, N
3
содержит α(2
n
3
) двоек и т. д. Таким
образом,
α(n) = α(2
n
1
) + α(2
n
2
) + . . . + α(2
n
k
). (5.70)
Для первых нескольких n утверждения леммы проверяются
непосредственно. Предположим их справедливость для всех n, дво-
ичная запись которых содержит не более k − 1 разрядов. Тогда
для числа n, состоящего из k разрядов, справедливо (5.70) при
α(2
n
i
) = 2
n
i
−1, так что
α(n) = 2
n
1
+ 2
n
2
+ . . . + 2
n
k
−k = n − β(n),
что по индукции доказывает лемму.
61
Страницы
- « первая
- ‹ предыдущая
- …
- 59
- 60
- 61
- 62
- 63
- …
- следующая ›
- последняя »
