Метка: оценка неравенствами

Условие

$\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}$, что и требовалось доказать.