Единственность разложения натурального числа по степеням 2

[VfuVfn]

Привет.
Нужно доказать, что каждое натуральное число единственным образом представляется в виде суммы неповторяющихся степеней двойки.
Доказываю по индукции.
База: $m = 0, 2^m = 1$
Предположение: Для $n\leqslant2^m$ вышесказанное верно.
Шаг: Рассмотрим $k=n-2^m, n<k<2^{m+1}$ - а дальше у меня затык...
Подскажите как доказать единственность?

[bot]

$1+2+2^2+\ldots+2^{n-1}=2^{n}-1<2^n.$

[VfuVfn]

развернуть можно? не понимаю как использлвать

[Brukvalub]

Рассмотрим суммы$ \sum_{i=0}^na_i\cdot 2^i $, где каждый коэффициент $ a_i$ может принять значение $0$ или $1$ .
Какое минимальное и максимальное значение может принять такая сумма, и сколько разных сумм образуется при фиксированном $n$?
Правильные ответы на эти вопросы все решают.

[VfuVfn]

Минимальная сумма - 0, максимальная $2^{n-1}$,разных сумм - $2^n$, так?

[ewert]

Brukvalub в сообщении #1109416 писал(а):

, и сколько разных сумм образуется при фиксированном $n$?

Совершенно лишний вопрос.

Brukvalub в сообщении #1109416 писал(а):

Какое минимальное и максимальное значение может принять такая сумма

Минимальная тоже ни к чему, а вот максимальная -- в точку.

Исходный вопрос эквивалентен следующему: можно ли представить ноль как сумму плюс-минус степеней двойки? Или, что опять же эквивалентно: может ли некоторая степень двойки равняться аналогичной комбинации предыдущих степеней?

[VfuVfn]

Вот так, предположим что есть 2 представления числа по степеням, в каждом из них выберем наибольшую степень 2. В первом это будет $2^m$, тогда во втором это будет $2^{m-1}$ т.к. $2^m=2^{m-1}+..+2^1+1$ и тогда $2^m$ больше чем сумма $2^{m-1}+..+2^1+1$ - получили противоречие.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задач(и). Подсказок было уже достаточно.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[ewert]

VfuVfn в сообщении #1109474 писал(а):

в каждом из них выберем наибольшую степень 2. В первом это будет $2^m$, тогда во втором это будет $2^{m-1}$

Не обязательно.

[svv]

VfuVfn в сообщении #1109474 писал(а):

в каждом из них выберем наибольшую степень 2

Не просто наибольшую степень 2. Очевидно, что существует такая наибольшая степень 2, которая в одно число входит, а в другое нет. (Наибольшая — значит, «выше» всё совпадает.) От этого и отталкивайтесь.

[Sinoid]

А еще можно почитать, как похожий вопрос решается, к примеру, у Куликова.

[VfuVfn]

Ок - в каждом из представлении разложении степеней оставим только различающиеся слагаемые степеней 2. в каждом наборе выберем наибольшую степень 2. В первом такое слагаемое будет не превосходить $2^m$, а втором $2^{m-1}$, потом переход к сравнению $2^m$ и суммы $2^{m-1}+...+1$ Так?
Куликов - дискретная математики - это?

[Sinoid]

VfuVfn в сообщении #1109616 писал(а):

Куликов - дискретная математики - это?

Нет, Алгебра и теория чисел, книга довольно-таки старая, но тем не менее и оттуда можно многое почерпнуть, но не все.

[svv]

Да. Допустим, такая наибольшая степень $m$: в первом числе она есть, а во втором нет.

Тогда даже если в первом числе степеней ниже $m$-й нет ни одной, а во втором числе степени ниже $m$-й есть все, всё равно первое число будет больше второго (на единичку), и равны они быть не могут.