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

Условие

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

Решение

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

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

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

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

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

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

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

Теперь, пусть [latex]n[/latex] — четно, [latex]l = \frac{n}{2}[/latex]. Получаем, [latex]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}}[/latex].
Если же [latex]n[/latex] — нечетно, то положим [latex]l = \frac{n — 1}{2}[/latex]. Тогда, [latex]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}}[/latex].
Таким образом, нужный результат доказан [latex]\forall n > 1[/latex]. Непосредственно проверяется, что и для [latex]n = 1[/latex] соответствующее неравенство справедливо.

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

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

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