10
$\begingroup$

The question I'm looking at, is to show that every positive integer $n$ can be written as a sum of distinct powers of two.

I can see that you can form any number based on the highest $2^t$ that is less than the number, plus some combination of $2^j's. And that you can make the number odd, by adding $2^0$ at the end.

I just don't know how to create the formula for the proof. I'm trying to figure out my base case, and then my inductive formula to figure out $k+1$, and I've got nothing.

  • 0
    Don't do induction on $n$. Do induction on $t$. the proposition isn't P(n) = "n can be written as a sum". It's P(t) = "Every n < 2^t can be written as a sum".2017-01-13

4 Answers 4

8

The statement is obviously true for $n=0$.

Assume that we are given an $n\geq1$ and that it is true for all $m$ with $0\leq m.

When $n=2m$ then $m and therefore $m=\sum_k 2^{p_k}$ with finitely many $p_k$, all of them different. It follows that $n=\sum_k 2^{p_k+1}$ with all $p_k+1$ different.

When $n=2m+1$ with an $m$ as before then $n=2^0+\sum_k 2^{p_k+1}$ with all $p_k+1$ different and different from $0$.

  • 0
    Sorry, I got it.2016-03-11
5

Finding such a representation is equivalent to expressing $n$ in binary. We can do induction as follows: Let $2^h$ be the highest power of $2$ less than or equal to $n.$ Then we must have $n-2^{h}< 2^{h+1} - 2^{h}=2^{h}(2-1)=2^{h}.$ Hence the greatest power, say $2^{g},$ of $2$ such that $2^{g}\le n-2^{h}$ must satisfy $g By strong induction on $h$ we can assume that $n-2^{h} = \sum_{i=0}^{h-1}c_i2^i$ where each $c_i$ is either $0$ or $1.$ But then we're done, since this implies $n= \sum_{i=0}^{h-1}c_i2^i + 2^h$ is a sum of distinct powers of $2.$

To be explicit, let's include the induction hypothesis. Namely, for $h=0$ every positive $n\le 2^h=2^0=1$ can be expressed as a power of $2,$ since the only possibility is $1=2^0.$ Thus, we assume that for a given $h>0$ and any $n\le2^h,$ that such a representation exists.

  • 0
    @labbhattacharjee I merely tried to give a proof of this fact, as it seemed to be the OP's goal to prove it usi$n$g i$n$duction. I'm not sure whether there can be a proof without induction.2012-07-30
3

Perhaps people will find this method easier...

$Proof$. We will use strong induction to prove that $\forall n \in \mathbb{Z}^+$ we can express $n$ as a sum of distinct powers of $2$.

Base Case. For $n=1$ note that $2^0=1$ and thus for $n=1$ our proposition holds.

Inductive Hypothesis. Assume $m\in\mathbb{Z}^+$ with $1\le m \le k$ and that our proposition holds for $m$.

Inductive Step. We consider two cases.

Case 1. If $k+1$ is even then observe that $\frac{k+1}{2}$ must be an integer. Now since $1\le \frac{k+1}{2} \le k$ we know by our inductive hypothesis that $\frac{k+1}{2}$ is the sum of distinct powers of $2$. But then multiplying $\frac{k+1}{2}$ by $2$ gives

$\frac{k+1}{2}\cdot2=k+1$

and since (by the distributive property of multiplication over addition) each distinct power of $2$ in the sum $\frac{k+1}{2}$ is multiplied by a factor of $2$, each power of $2$ is increased by $1$ and thus remains distinct.

Case 2. If $k+1$ is odd then we know $k$ is even. Furthermore we know by our inductive hypothesis that $k$ may expressed as the sum of distinct powers of $2$. But if $k$ is even we know $k$ does not contain a $2^0=1$ in its sum of distinct powers of $2$.

Remark: To observe that $2^0=1$ does not exist in the sum of distinct powers of $2$ that makeup $k$, note that $k$, by the definition of an even integer, may be expressed as $2m$ for some $m\in\mathbb{Z}^+$ (since $k$ is positive we limit $m$ to the positive integers) and since we can view multiplication as repeated addition we have $2m = 2 + 2 + \cdots + 2 + 2$ where we are taking the sum of $m$ twos. If the sum were to contain a $2^0=1$ we clearly would need to express our integer as $2m+1$ which would make it odd not even.

Thus we see that

$k+1=k + 2^0$

and if $k+1$ is odd we may express $k+1$ as the sum of distinct powers of $2$.

It follows by strong mathematical induction that $\forall n \in \mathbb{Z}^+$ we can express $n$ as a sum of distinct powers of $2$. $\Box$

-1

The subtle thing is the exact wording of the proposition.

If you want to prove:

$P(n) = $ $n$ can be expressed as a distinct sum of powers of $2$.

Initial case: $n = 1$ $P(1)$ is provable.

Induction step: $P(k) \implies P(k+1)$

then this is impossible. $P(k) \not \implies P(k+1)$ and there is simply no way to show it does.

But if instead you try to prove.

$Q(n) = $ of all $j; 0 < j < 2^n$, $j $ can be written as a distinct product of powers of $2$

then $Q(k) \implies Q(k+1)$ is pretty easy to prove.

(if $0 < j \le 2^{n+1}$ then either $j = m$ or $j = m + 2^n$ where $0 < m < 2^n$ so $m$ can be distinctly written as $\sum 2^i$. As $m < 2^n$ none of its powers of $2$ are to the $n$ power. So $m + 2^n = 2^n + \sum 2^i $ is a sum with distinct powers of $2$. So $j$, whethe $j = m$ or $j = m + 2^n$ can be written as a sum of distinct powers.)

...

Another way to view this, albeit, maybe not as rigorous. Is that induction need not be a direct $P(n) \implies P(n+1)$ progression. And $P(n) \implies P(f(n))$ where $\cup_{i \in \mathbb N} F_i= \mathbb N$ where $F_0 = \{1\text{ or } 0\}$ and $F_{i+1} = \{f(a)|a \in \cup_{k \le i}F_i\}$, qualifies as induction as well.

Here $f(n) = n + 2^k$ where $k$ is the smallest power where $2^k > n$.

(although the bit $\cup_{i \in \mathbb N} F_i= \mathbb N$ most likely will boil down to a $Q(n) \implies Q(n+1)$. e.g. How do we know $\{0,1\}, \{0,1, 2, 3\},\{0, 1, 2, 3,4,5,6,7\} ....$ will span $\mathbb N$? Probably by induction.)