M1630. О количестве способов представления натурального числа в виде суммы степеней двойки

Условие

\forall n \in N обозначим через f(n) число способов представления числа n в виде суммы целых неотрицательных степеней числа 2. Преставления, отличающиеся лишь порядком слагаемых, считаются одинаковыми. Например, f(4) = 4, так как число 4 может быть представлено следующими четырьмя способами:
4 = 4;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1.
Докажите, что \forall n \in N, n \geq 3: 2^{n^2/4} < f(2^n) < 2^{n^2/2}.

Решение

Если n = 2k + 1 — любое нечетное число, большее 1, то каждое его представление в требуемом по условию задачи виде содержит 1 в качестве слагаемого. Убрав эту единицу, мы получим представление числа 2k. Очевидно и обратное. Следовательно, f(2k + 1) = f(2k). (*)

Если n = 2k — любое четное число, то каждое его представление в требуемом виде принадлежит к одному из двух типов: либо оно содержит слагаемое 1, либо не
содержит таких слагаемых. В первом случае, убрав одно слагаемое 1, мы получим представление числа 2k - 1. Как и выше, легко заметить, что есть взаимно однозначное соответствие между всеми представлениями числа 2k - 1 и представлениями числа 2k первого типа. Во втором случае мы можем разделить все слагаемые
на 2 и получить представление числа k. Это соответствие также взаимно однозначно. Итак, f(2k) = f(2k - 1) + f(k). (**)

Обе полученные формулы выполнены для всех натуральных k > 1. Очевидно, что f(1) = 1. Пусть по определению f(0) = 1, тогда формула (*) выполнена и при k = 0. Заметим еще, что из (*) и (**) следует, что f(n) не убывает.

Согласно (*), число f(2k - 1) в (**) можно заменить на
f(2k - 2), откуда f(2k) - f(2k - 2) = f(k) \forall k \geq 1. Суммируя эти равенства от 1 до n, получаем, что f(2n) = \sum_{i=0}^n f(i). (***)
В правой части (***) каждое слагаемое не больше последнего, а так как 2 = f(0) + f(1) \leq f(n) \forall n \geq 2, то f(2n) = 2 + \sum_{i=2}^n f(i) \leq 2 + (n - 1)f(n) \leq f(n) + (n - 1)f(n) \leq nf(n) \forall n \geq 2. Следовательно, f(2^n) \leq 2^{n-1}f(2^{n-1}) \leq 2^{n-1}2^{n-2}f(2^{n-2}) \leq \ldots \leq 2^{(n-1) + (n-2) + \ldots + 2 + 1}f(2) = 2^{\frac{n(n-1)}{2} + 1}.
И так как \frac{n(n-1)}{2} + 1 < \frac{n^2}{2}, т.е. 2^{\frac{n(n-1)}{2} + 1} < 2^{\frac{n^2}{2}} \forall n \geq 3, верхняя оценка для f(2n) получена.

Чтобы получить нижнюю оценку, докажем сначала, что f(b + 1) - f(b) \geq f(a + 1) - f(a) (4), если 0 \leq a \leq b — целые числа одинаковой четности. Действительно, если a и b четны, то из (*) следует,что каждая часть неравенства (4) обращается в нуль, если они оба нечетны, то из (**) следует, что f(b + 1) - f(b) = f(\frac{b+1}{2}), f(a + 1) - f(a) = f(\frac{a+1}{2}), при чем, как было показано ранее, f не убывает.

Возьмем произвольные r и k, r \geq k, r — четное. Подставим в неравенство (4) a = r + j, b = r - j, j = 0, 1, \ldots, k - 1. Получаем следующий набор неравенств:
j = 0 : \underline{f(r + 1)} - f(r) \geq f(r + 1) - \underline{f(r)}
j = 1 : \underline{f(r + 2)} - \underline{f(r + 1)} \geq \underline{f(r)} - \underline{f(r - 1)}
j = 2 : \underline{f(r + 3)} - \underline{f(r + 2)} \geq \underline{f(r - 1)} - \underline{f(r - 2)}
(…)
j = k - 2 : \underline{f(r + k - 1)} - \underline{f(r + k - 2)} \geq \underline{f(r + k - 3)} - \underline{f(r + k - 2)}
j = k - 1 : f(r + k) - \underline{f(r + k - 1)} \geq \underline{f(r + k - 2)} - f(r + k - 1)
Просуммировав левые и правые части неравенств соответственно, легко увидеть, что все промежуточные слагаемые сокращаются, и остается следующее: f(r + k) - f(r) \geq f(r + 1) - f(r - k + 1), а в силу того, что r — четное и f(r + 1) = f(r), получим f(r + k) + f(r - k + 1) \geq 2f(r). Так как r \geq k, просуммируем уже такие неравенства по k = 1, 2, \ldots, r, и получим \sum_{i=1}^{2r}f(i) \geq 2rf(r), или, что тоже самое \sum_{i=0}^{2r}f(i) - f(0) \geq 2rf(r). В силу (***) \sum_{i=0}^{2r}f(i) = f(4r), а f(0) = 1. Получаем следующее неравенство: f(4r) \geq 2rf(r) + 1 > 2rf(r). Возьмем r = 2^{m - 2}, тогда f(2^m) > 2^{m - 1}f(2^{m - 2}). (5)
(Очевидно, что \forall m \in N, m > 2: 2^{m - 2} — четно. Также, непосредственно подстановкой легко убедиться, что неравенство (5) справедливо и при m = 2: f(4) = 4 > 2 = f(2)f(1).)

Наконец. пусть n \in N, n > 1. Если l — положительное целое такое, что 2l \leq n, то применяя неравенство (5) к m = n, n - 1, \ldots, n -2l + 2, получаем:
f(2^n) > 2^{n - 1}f(2^{n - 2}) > 2^{n - 1}2^{n - 3}f(2^{n - 4}) > \ldots > 2^{(n - 1) + (n - 3) + \ldots + (n - 2l + 1)}f(2^{n - 2l}) = 2^{l(n - 2l)}f(2^{n - 2l}) (слагаемых в показателе степени — l штук, а 1 + 3 + \ldots + (2l - 1) = l^2, тогда (n - 1) + (n - 3) + \ldots + (n - 2l + 1) = nl - l^2 = l(n - l)).

Теперь, пусть n — четно, l = \frac{n}{2}. Получаем, f(2^n) > 2^{\frac{n}{2}(n - \frac{n}{2})}f(2^0) = 2^{\frac{n^2}{4}}f(1) = 2^{\frac{n^2}{4}}.
Если же n — нечетно, то положим l = \frac{n - 1}{2}. Тогда, f(2^n) > 2^{\frac{n - 1}{2}(n - \frac{n - 1}{2})}f(2^1) = 2^{\frac{(n - 1)(n + 1)}{4}}f(2) = 2^{\frac{n^2 - 1}{4} + 1} = 2^{\frac{n^2 + 3}{4}} > 2^{\frac{n^2}{4}}.
Таким образом, нужный результат доказан \forall n > 1. Непосредственно проверяется, что и для n = 1 соответствующее неравенство справедливо.

Тогда получаем, что \forall n \in N, n \geq 3: 2^{n^2/4} < f(2^n) < 2^{n^2/2}, что и требовалось доказать.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *