Докажите, что каждое натуральное число n может быть единственным образом представлено в виде n=a1 ·1!+a2 ·2!+a3 ·3!+..., где 0<=а1<=1 0<=а2<=2 ,0<=а3 <=3,... И т д

задан 10 Ноя '15 19:01

1

Доказательство основывается на тождестве $$1\cdot1!+2\cdot2!+...+n\cdot n!=(n+1)!-1.$$

(10 Ноя '15 21:01) EdwardTurJ

я не понимаю, как основывая на выше сказанном тождестве, можно доказать утверждение

(10 Ноя '15 21:56) NataliaIvanova
10|600 символов нужно символов осталось
1

Всякое натуральное число находится между какими-то факториалами: $%m!\le n < (m+1)!$%. Докажем, что оно представимо в виде $%n=a_1\cdot1!+a_2\cdot2!+\cdots+a_m\cdot m!$%, где $%0\le a_k\le k$% для всех $%k$%. Доказательство будем вести при помощи индукции по $%m$%. Если $%m=1$%, то $%n=1$%, и тогда берём $%a_1=1$%.

Пусть $%m > 1$%. Ввиду того, что $%1\le\frac{n}{m!} < m+1$%, целая часть дроби принимает значения от $%1$% до $%m$%. Положим $%a_m=[\frac{n}{m!}]$%. Тогда для $%a_m$% требуемое неравенство выполняется, и $%a_m\cdot m!\le n < (a_m+1)m!$%. Тогда $%0\le n-a_m\cdot m! < m!$%, и можно применить предположение индукции для числа $%n-a_m\cdot m!$%, которое находится между факториалами с меньшими значениями по сравнению с числом $%n$%. Тогда для него существуют подходящие числа $%a_1$%, ... , $%a_{m-1}$% такие, что $%n-a_m\cdot m!=a_1\cdot1!+a_2\cdot2!+\cdots+a_{m-1}\cdot(m-1)!$%, с выполнением всех неравенств для чисел вида $%a_i$%. Сюда также включается случай, когда все $%a_i$% равны нулю. Тем самым, число $%n$% также представляется в нужном виде.

Теперь осталось доказать единственность. Допустим, что мы представили число $%n$% двумя разными способами. Рассмотрим старшие разряды, которые отличаются. Игнорируя совпадающие разряды, можно считать, что $%a_1\cdot1!+a_2\cdot2!+\cdots+a_m\cdot m!=b_1\cdot1!+b_2\cdot2!+\cdots+b_m\cdot m!$%, где $%a_m > b_m$%. Но тогда, выбирая $%a_i$% минимально возможными, то есть равными нулю, а $%b_i$% максимально возможными, то есть равными $%i$%, мы получаем неравенство $%m!\le(a_m-b_m)\cdot m!\le1\cdot1!+2\cdot2!+\cdots+(m-1)\cdot(m-1)!=m!-1$%, что даёт противоречие.

P.S. Это доказательство в обе стороны совершенно "рутинно", и оно принципиально мало чем отличается от доказательства существования и единственности представления чисел в обычных позиционных системах счисления.

ссылка

отвечен 10 Ноя '15 22:33

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

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

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

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

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

отмечен:

×109
×80
×44

задан
10 Ноя '15 19:01

показан
2192 раза

обновлен
10 Ноя '15 22:33

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

по почте:

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

по RSS:

Ответы

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

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