Доказать неравенство |M_n|<= |M_n-2|^2 * 2^(2^(n-2))

задан 4 Окт '17 20:53

10|600 символов нужно символов осталось
0

Будем доказывать неравенство в виде $%|M_{n+2}|\le|M_n|^22^{2^n}$% при $%n\ge0$%. Пусть $%f(X,x_{n+1},x_{n+2})$% -- монотонная функция от $%n+2$% переменных, где $%X$% есть сокращённое обозначение для последовательности $%x_1,\ldots,x_n$%. Фиксация значений любых переменных даёт монотонную функцию. Тем самым, функции $%f(X,0,1)$% и $%f(X,1,0)$% монотонны, и каждая из них может принимать не более $%|M_n|$% значений. Пара таких функций принимает не более $%|M_n|^2$% значений.

Из монотонности функции $%f$% следуют неравенства $%f(X,0,0)\le f(X,0,1)\le f(X,1,1)$%. Аналогичные неравенства верны и для случая $%f(X,1,0)$%, но их мы привлекать не будем.

При отсутствии таких неравенств, значения для $%f(X,0,0)$% и $%f(X,1,1)$% выбираются при каждом фиксированном наборе $%X$% четырьмя способами. Покажем, что в нашей ситуации способов не более двух. Действительно, если $%f(X,0,1)=0$%, то $%f(X,0,0)=0$% определяется однозначно, а $%f(X,1,1)$% может принимать два значения. А если $%f(X,0,1)=1$%, то всё наоборот: $%f(X,1,1)=1$% определяется однозначно, а $%f(X,0,0)$% может принимать два значения.

Таким образом, для каждого из $%2^n$% наборов вида $%X$% мы имеем два способа задания значений $%f(X,0,0)$% и $%f(X,1,1)$%. Всего получается не более $%2^{2^n}$% способов задать эти значения по всем наборам. Полученная информация однозначно задаёт $%f$%. Перемножая две величины по правилу произведения, имеем верхнюю оценку в неравенстве.

ссылка

отвечен 5 Окт '17 3:52

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,333
×819
×150

задан
4 Окт '17 20:53

показан
204 раза

обновлен
5 Окт '17 3:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru