Mixing
Sum of all powers of two
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
Prove that for any positive integer $n$, there exists a nonnegative integer $k$ with the property that $n$ can be written as a sum of the numbers $2^0,2^1,dots,2^k$, each appearing once or twice.
It seems that we should begin with the canonical representation of $n$ as a sum of powers of two. To make sure that every powers of two appears, we will need to "break down" some powers of two to fill in the gaps.
elementary-number-theory
asked Sep 9 at 1:39
pi66
3,7971037
add a comment |Â
up vote
6
down vote
favorite
Prove that for any positive integer $n$, there exists a nonnegative integer $k$ with the property that $n$ can be written as a sum of the numbers $2^0,2^1,dots,2^k$, each appearing once or twice.
It seems that we should begin with the canonical representation of $n$ as a sum of powers of two. To make sure that every powers of two appears, we will need to "break down" some powers of two to fill in the gaps.
elementary-number-theory
asked Sep 9 at 1:39
pi66
3,7971037
1
This is an odd question. Did this come from a course? If so, which course, and what kind of results/techniques have you covered recently? I ask, because it might affect which answer I'd give.
– Theo Bendit
Sep 9 at 1:59
You seem to have a good idea about approaching the problem, starting from the canonical binary expansion and splitting one or more higher powers to fill in gaps. Doing some modest size examples should illustrate how you might use induction or well-ordering to formally package a proof.
– hardmath
Sep 9 at 2:09
1
Bijective numeration.
– user202729
Sep 9 at 13:41
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
Prove that for any positive integer $n$, there exists a nonnegative integer $k$ with the property that $n$ can be written as a sum of the numbers $2^0,2^1,dots,2^k$, each appearing once or twice.
It seems that we should begin with the canonical representation of $n$ as a sum of powers of two. To make sure that every powers of two appears, we will need to "break down" some powers of two to fill in the gaps.
elementary-number-theory
asked Sep 9 at 1:39
pi66
3,7971037
Prove that for any positive integer $n$, there exists a nonnegative integer $k$ with the property that $n$ can be written as a sum of the numbers $2^0,2^1,dots,2^k$, each appearing once or twice.
It seems that we should begin with the canonical representation of $n$ as a sum of powers of two. To make sure that every powers of two appears, we will need to "break down" some powers of two to fill in the gaps.
elementary-number-theory
elementary-number-theory
asked Sep 9 at 1:39
pi66
3,7971037
asked Sep 9 at 1:39
pi66
3,7971037
asked Sep 9 at 1:39
pi66
3,7971037
asked Sep 9 at 1:39
pi66
3,7971037
asked Sep 9 at 1:39
pi66
3,7971037
3,7971037
1
This is an odd question. Did this come from a course? If so, which course, and what kind of results/techniques have you covered recently? I ask, because it might affect which answer I'd give.
– Theo Bendit
Sep 9 at 1:59
You seem to have a good idea about approaching the problem, starting from the canonical binary expansion and splitting one or more higher powers to fill in gaps. Doing some modest size examples should illustrate how you might use induction or well-ordering to formally package a proof.
– hardmath
Sep 9 at 2:09
1
Bijective numeration.
– user202729
Sep 9 at 13:41
add a comment |Â
1
This is an odd question. Did this come from a course? If so, which course, and what kind of results/techniques have you covered recently? I ask, because it might affect which answer I'd give.
– Theo Bendit
Sep 9 at 1:59
You seem to have a good idea about approaching the problem, starting from the canonical binary expansion and splitting one or more higher powers to fill in gaps. Doing some modest size examples should illustrate how you might use induction or well-ordering to formally package a proof.
– hardmath
Sep 9 at 2:09
1
Bijective numeration.
– user202729
Sep 9 at 13:41
1
1
This is an odd question. Did this come from a course? If so, which course, and what kind of results/techniques have you covered recently? I ask, because it might affect which answer I'd give.
– Theo Bendit
Sep 9 at 1:59
This is an odd question. Did this come from a course? If so, which course, and what kind of results/techniques have you covered recently? I ask, because it might affect which answer I'd give.
– Theo Bendit
Sep 9 at 1:59
You seem to have a good idea about approaching the problem, starting from the canonical binary expansion and splitting one or more higher powers to fill in gaps. Doing some modest size examples should illustrate how you might use induction or well-ordering to formally package a proof.
– hardmath
Sep 9 at 2:09
You seem to have a good idea about approaching the problem, starting from the canonical binary expansion and splitting one or more higher powers to fill in gaps. Doing some modest size examples should illustrate how you might use induction or well-ordering to formally package a proof.
– hardmath
Sep 9 at 2:09
1
1
Bijective numeration.
– user202729
Sep 9 at 13:41
Bijective numeration.
– user202729
Sep 9 at 13:41
add a comment |Â
5 Answers
5
active
oldest
votes
up vote
4
down vote
accepted
Basically, as you say, fill in the gaps. We can always write a positive integer $n$ as a sum of powers of $2$ using the binary expansion:
$$n = delta_0 2^0 + delta_1 2^1 + ldots + delta_k 2^k,$$
where $delta_i in lbrace 0, 1rbrace$. Take the least $m$ such that $delta_i = 0$, and consider the least $l > m$ such that $delta_l = 1$. Then, we can write:
$$n = 2^0 + ldots + 2^m-1 + 2cdot 2^m + 2^m+1 + ldots + 2^l-1 + delta_l+1 2^l+1 + ldots + delta_k 2^k.$$
Note that, while this doesn't necessarily reduce the number of gaps, it does push the start of the first gap further along. You could consider using strong induction on $lfloorlog_2(n)rfloor - m$, where $m$ is the start of the first gap.
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
add a comment |Â
up vote
5
down vote
Consider the binary representation of $,n+1 = 2^k+1+sum_j=0^k b_j 2^j ;mid; b_j in 0,1,$, then:
$$n = 2^k+1-1+sum_j=0^k b_j2^j = sum_j=0^k 2^j+sum_j=0^k b_j2^j = sum_j=0^k (b_j+1)2^j quad stylefont-family:inherittextwhere;; b_j+1 in 1,2$$
answered Sep 9 at 2:53
dxiv
55.8k64798
add a comment |Â
up vote
3
down vote
Given any binary string $overlineb_ndots b_1b_0(b_iin 0, 1, b_n = 1)$ , consider the following procedure:
Repeat 1, 2, and 3 until the string does not contain '0':
- $10mapsto 02$: If $overlineb_j +1b_j = 10$, let $overlineb_j +1b_j gets02$.
- Delete the highest digit if it is 0.
- $20mapsto 12$: If $overlineb_j +1b_j = 20$, let $overlineb_j +1b_j gets 12$.
The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = maxicolon b_i = 0$ for string $overlineb_ndots b_1b_0$, then $m leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps.
As an example, given '110101', this procedure gives
$110101 mapsto 102021 mapsto 101221 mapsto 021221 mapsto 21221$.
answered Sep 9 at 2:24
Xiangxiang Xu
81948
add a comment |Â
up vote
1
down vote
The following statements are equivalent:
$$n=c_02^0+c_12^1+cdots+c_k2^ktext for some c_0,c_1,dots,c_kin1,2$$
$$n=2^0+2^1+cdots+2^k+mtext where 0le mle2^0+2^1+cdots+2^k$$
$$2^0+2^1+cdots+2^kle nle2(2^0+2^1+cdots+2^k)$$
$$2^k+1-1le nle2^k+2-2$$
$$2^k+1-1le nlt2^k+2-1$$
$$2^k+1le n+1lt2^k+2$$
$$k+1lelog_2(n+1)lt k+2$$
$$k+1=lfloorlog_2(n+1)rfloor$$
$$k=lfloorlog_2(n+1)rfloor-1$$
answered Sep 9 at 3:03
bof
46.7k349113
add a comment |Â
up vote
0
down vote
If you can write all numbers from $0$ to $2^n-1$ using sums of powers of $2$ from $2^0$ to $2^n-1$, then you can write any number from $0$ to $2^n+1-1$ using sums of powers of $2$ from $2^0$ to $2^n$ by representing it as the number from $0$ to $2^n-1$ and then adding $2^n$. The property holds for $n=0$, therefore by induction it holds for all $n$.
answered Sep 9 at 10:52
Jack M
17.6k33574
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
Basically, as you say, fill in the gaps. We can always write a positive integer $n$ as a sum of powers of $2$ using the binary expansion:
$$n = delta_0 2^0 + delta_1 2^1 + ldots + delta_k 2^k,$$
where $delta_i in lbrace 0, 1rbrace$. Take the least $m$ such that $delta_i = 0$, and consider the least $l > m$ such that $delta_l = 1$. Then, we can write:
$$n = 2^0 + ldots + 2^m-1 + 2cdot 2^m + 2^m+1 + ldots + 2^l-1 + delta_l+1 2^l+1 + ldots + delta_k 2^k.$$
Note that, while this doesn't necessarily reduce the number of gaps, it does push the start of the first gap further along. You could consider using strong induction on $lfloorlog_2(n)rfloor - m$, where $m$ is the start of the first gap.
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
add a comment |Â
up vote
4
down vote
accepted
Basically, as you say, fill in the gaps. We can always write a positive integer $n$ as a sum of powers of $2$ using the binary expansion:
$$n = delta_0 2^0 + delta_1 2^1 + ldots + delta_k 2^k,$$
where $delta_i in lbrace 0, 1rbrace$. Take the least $m$ such that $delta_i = 0$, and consider the least $l > m$ such that $delta_l = 1$. Then, we can write:
$$n = 2^0 + ldots + 2^m-1 + 2cdot 2^m + 2^m+1 + ldots + 2^l-1 + delta_l+1 2^l+1 + ldots + delta_k 2^k.$$
Note that, while this doesn't necessarily reduce the number of gaps, it does push the start of the first gap further along. You could consider using strong induction on $lfloorlog_2(n)rfloor - m$, where $m$ is the start of the first gap.
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
Basically, as you say, fill in the gaps. We can always write a positive integer $n$ as a sum of powers of $2$ using the binary expansion:
$$n = delta_0 2^0 + delta_1 2^1 + ldots + delta_k 2^k,$$
where $delta_i in lbrace 0, 1rbrace$. Take the least $m$ such that $delta_i = 0$, and consider the least $l > m$ such that $delta_l = 1$. Then, we can write:
$$n = 2^0 + ldots + 2^m-1 + 2cdot 2^m + 2^m+1 + ldots + 2^l-1 + delta_l+1 2^l+1 + ldots + delta_k 2^k.$$
Note that, while this doesn't necessarily reduce the number of gaps, it does push the start of the first gap further along. You could consider using strong induction on $lfloorlog_2(n)rfloor - m$, where $m$ is the start of the first gap.
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
Basically, as you say, fill in the gaps. We can always write a positive integer $n$ as a sum of powers of $2$ using the binary expansion:
$$n = delta_0 2^0 + delta_1 2^1 + ldots + delta_k 2^k,$$
where $delta_i in lbrace 0, 1rbrace$. Take the least $m$ such that $delta_i = 0$, and consider the least $l > m$ such that $delta_l = 1$. Then, we can write:
$$n = 2^0 + ldots + 2^m-1 + 2cdot 2^m + 2^m+1 + ldots + 2^l-1 + delta_l+1 2^l+1 + ldots + delta_k 2^k.$$
Note that, while this doesn't necessarily reduce the number of gaps, it does push the start of the first gap further along. You could consider using strong induction on $lfloorlog_2(n)rfloor - m$, where $m$ is the start of the first gap.
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
answered Sep 9 at 2:13
Theo Bendit
12.9k1944
12.9k1944
add a comment |Â
add a comment |Â
up vote
5
down vote
Consider the binary representation of $,n+1 = 2^k+1+sum_j=0^k b_j 2^j ;mid; b_j in 0,1,$, then:
$$n = 2^k+1-1+sum_j=0^k b_j2^j = sum_j=0^k 2^j+sum_j=0^k b_j2^j = sum_j=0^k (b_j+1)2^j quad stylefont-family:inherittextwhere;; b_j+1 in 1,2$$
answered Sep 9 at 2:53
dxiv
55.8k64798
add a comment |Â
up vote
5
down vote
Consider the binary representation of $,n+1 = 2^k+1+sum_j=0^k b_j 2^j ;mid; b_j in 0,1,$, then:
$$n = 2^k+1-1+sum_j=0^k b_j2^j = sum_j=0^k 2^j+sum_j=0^k b_j2^j = sum_j=0^k (b_j+1)2^j quad stylefont-family:inherittextwhere;; b_j+1 in 1,2$$
answered Sep 9 at 2:53
dxiv
55.8k64798
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Consider the binary representation of $,n+1 = 2^k+1+sum_j=0^k b_j 2^j ;mid; b_j in 0,1,$, then:
$$n = 2^k+1-1+sum_j=0^k b_j2^j = sum_j=0^k 2^j+sum_j=0^k b_j2^j = sum_j=0^k (b_j+1)2^j quad stylefont-family:inherittextwhere;; b_j+1 in 1,2$$
answered Sep 9 at 2:53
dxiv
55.8k64798
Consider the binary representation of $,n+1 = 2^k+1+sum_j=0^k b_j 2^j ;mid; b_j in 0,1,$, then:
$$n = 2^k+1-1+sum_j=0^k b_j2^j = sum_j=0^k 2^j+sum_j=0^k b_j2^j = sum_j=0^k (b_j+1)2^j quad stylefont-family:inherittextwhere;; b_j+1 in 1,2$$
answered Sep 9 at 2:53
dxiv
55.8k64798
answered Sep 9 at 2:53
dxiv
55.8k64798
answered Sep 9 at 2:53
dxiv
55.8k64798
answered Sep 9 at 2:53
dxiv
55.8k64798
55.8k64798
add a comment |Â
add a comment |Â
up vote
3
down vote
Given any binary string $overlineb_ndots b_1b_0(b_iin 0, 1, b_n = 1)$ , consider the following procedure:
Repeat 1, 2, and 3 until the string does not contain '0':
- $10mapsto 02$: If $overlineb_j +1b_j = 10$, let $overlineb_j +1b_j gets02$.
- Delete the highest digit if it is 0.
- $20mapsto 12$: If $overlineb_j +1b_j = 20$, let $overlineb_j +1b_j gets 12$.
The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = maxicolon b_i = 0$ for string $overlineb_ndots b_1b_0$, then $m leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps.
As an example, given '110101', this procedure gives
$110101 mapsto 102021 mapsto 101221 mapsto 021221 mapsto 21221$.
answered Sep 9 at 2:24
Xiangxiang Xu
81948
add a comment |Â
up vote
3
down vote
Given any binary string $overlineb_ndots b_1b_0(b_iin 0, 1, b_n = 1)$ , consider the following procedure:
Repeat 1, 2, and 3 until the string does not contain '0':
- $10mapsto 02$: If $overlineb_j +1b_j = 10$, let $overlineb_j +1b_j gets02$.
- Delete the highest digit if it is 0.
- $20mapsto 12$: If $overlineb_j +1b_j = 20$, let $overlineb_j +1b_j gets 12$.
The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = maxicolon b_i = 0$ for string $overlineb_ndots b_1b_0$, then $m leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps.
As an example, given '110101', this procedure gives
$110101 mapsto 102021 mapsto 101221 mapsto 021221 mapsto 21221$.
answered Sep 9 at 2:24
Xiangxiang Xu
81948
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Given any binary string $overlineb_ndots b_1b_0(b_iin 0, 1, b_n = 1)$ , consider the following procedure:
Repeat 1, 2, and 3 until the string does not contain '0':
- $10mapsto 02$: If $overlineb_j +1b_j = 10$, let $overlineb_j +1b_j gets02$.
- Delete the highest digit if it is 0.
- $20mapsto 12$: If $overlineb_j +1b_j = 20$, let $overlineb_j +1b_j gets 12$.
The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = maxicolon b_i = 0$ for string $overlineb_ndots b_1b_0$, then $m leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps.
As an example, given '110101', this procedure gives
$110101 mapsto 102021 mapsto 101221 mapsto 021221 mapsto 21221$.
answered Sep 9 at 2:24
Xiangxiang Xu
81948
Given any binary string $overlineb_ndots b_1b_0(b_iin 0, 1, b_n = 1)$ , consider the following procedure:
Repeat 1, 2, and 3 until the string does not contain '0':
- $10mapsto 02$: If $overlineb_j +1b_j = 10$, let $overlineb_j +1b_j gets02$.
- Delete the highest digit if it is 0.
- $20mapsto 12$: If $overlineb_j +1b_j = 20$, let $overlineb_j +1b_j gets 12$.
The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = maxicolon b_i = 0$ for string $overlineb_ndots b_1b_0$, then $m leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps.
As an example, given '110101', this procedure gives
$110101 mapsto 102021 mapsto 101221 mapsto 021221 mapsto 21221$.
answered Sep 9 at 2:24
Xiangxiang Xu
81948
edited Sep 9 at 2:46
answered Sep 9 at 2:24
Xiangxiang Xu
81948
answered Sep 9 at 2:24
Xiangxiang Xu
81948
answered Sep 9 at 2:24
Xiangxiang Xu
81948
81948
add a comment |Â
add a comment |Â
up vote
1
down vote
The following statements are equivalent:
$$n=c_02^0+c_12^1+cdots+c_k2^ktext for some c_0,c_1,dots,c_kin1,2$$
$$n=2^0+2^1+cdots+2^k+mtext where 0le mle2^0+2^1+cdots+2^k$$
$$2^0+2^1+cdots+2^kle nle2(2^0+2^1+cdots+2^k)$$
$$2^k+1-1le nle2^k+2-2$$
$$2^k+1-1le nlt2^k+2-1$$
$$2^k+1le n+1lt2^k+2$$
$$k+1lelog_2(n+1)lt k+2$$
$$k+1=lfloorlog_2(n+1)rfloor$$
$$k=lfloorlog_2(n+1)rfloor-1$$
answered Sep 9 at 3:03
bof
46.7k349113
add a comment |Â
up vote
1
down vote
The following statements are equivalent:
$$n=c_02^0+c_12^1+cdots+c_k2^ktext for some c_0,c_1,dots,c_kin1,2$$
$$n=2^0+2^1+cdots+2^k+mtext where 0le mle2^0+2^1+cdots+2^k$$
$$2^0+2^1+cdots+2^kle nle2(2^0+2^1+cdots+2^k)$$
$$2^k+1-1le nle2^k+2-2$$
$$2^k+1-1le nlt2^k+2-1$$
$$2^k+1le n+1lt2^k+2$$
$$k+1lelog_2(n+1)lt k+2$$
$$k+1=lfloorlog_2(n+1)rfloor$$
$$k=lfloorlog_2(n+1)rfloor-1$$
answered Sep 9 at 3:03
bof
46.7k349113
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The following statements are equivalent:
$$n=c_02^0+c_12^1+cdots+c_k2^ktext for some c_0,c_1,dots,c_kin1,2$$
$$n=2^0+2^1+cdots+2^k+mtext where 0le mle2^0+2^1+cdots+2^k$$
$$2^0+2^1+cdots+2^kle nle2(2^0+2^1+cdots+2^k)$$
$$2^k+1-1le nle2^k+2-2$$
$$2^k+1-1le nlt2^k+2-1$$
$$2^k+1le n+1lt2^k+2$$
$$k+1lelog_2(n+1)lt k+2$$
$$k+1=lfloorlog_2(n+1)rfloor$$
$$k=lfloorlog_2(n+1)rfloor-1$$
answered Sep 9 at 3:03
bof
46.7k349113
The following statements are equivalent:
$$n=c_02^0+c_12^1+cdots+c_k2^ktext for some c_0,c_1,dots,c_kin1,2$$
$$n=2^0+2^1+cdots+2^k+mtext where 0le mle2^0+2^1+cdots+2^k$$
$$2^0+2^1+cdots+2^kle nle2(2^0+2^1+cdots+2^k)$$
$$2^k+1-1le nle2^k+2-2$$
$$2^k+1-1le nlt2^k+2-1$$
$$2^k+1le n+1lt2^k+2$$
$$k+1lelog_2(n+1)lt k+2$$
$$k+1=lfloorlog_2(n+1)rfloor$$
$$k=lfloorlog_2(n+1)rfloor-1$$
answered Sep 9 at 3:03
bof
46.7k349113
answered Sep 9 at 3:03
bof
46.7k349113
answered Sep 9 at 3:03
bof
46.7k349113
answered Sep 9 at 3:03
bof
46.7k349113
46.7k349113
add a comment |Â
add a comment |Â
up vote
0
down vote
If you can write all numbers from $0$ to $2^n-1$ using sums of powers of $2$ from $2^0$ to $2^n-1$, then you can write any number from $0$ to $2^n+1-1$ using sums of powers of $2$ from $2^0$ to $2^n$ by representing it as the number from $0$ to $2^n-1$ and then adding $2^n$. The property holds for $n=0$, therefore by induction it holds for all $n$.
answered Sep 9 at 10:52
Jack M
17.6k33574
add a comment |Â
up vote
0
down vote
If you can write all numbers from $0$ to $2^n-1$ using sums of powers of $2$ from $2^0$ to $2^n-1$, then you can write any number from $0$ to $2^n+1-1$ using sums of powers of $2$ from $2^0$ to $2^n$ by representing it as the number from $0$ to $2^n-1$ and then adding $2^n$. The property holds for $n=0$, therefore by induction it holds for all $n$.
answered Sep 9 at 10:52
Jack M
17.6k33574
add a comment |Â
up vote
0
down vote
up vote
0
down vote
If you can write all numbers from $0$ to $2^n-1$ using sums of powers of $2$ from $2^0$ to $2^n-1$, then you can write any number from $0$ to $2^n+1-1$ using sums of powers of $2$ from $2^0$ to $2^n$ by representing it as the number from $0$ to $2^n-1$ and then adding $2^n$. The property holds for $n=0$, therefore by induction it holds for all $n$.
answered Sep 9 at 10:52
Jack M
17.6k33574
If you can write all numbers from $0$ to $2^n-1$ using sums of powers of $2$ from $2^0$ to $2^n-1$, then you can write any number from $0$ to $2^n+1-1$ using sums of powers of $2$ from $2^0$ to $2^n$ by representing it as the number from $0$ to $2^n-1$ and then adding $2^n$. The property holds for $n=0$, therefore by induction it holds for all $n$.
answered Sep 9 at 10:52
Jack M
17.6k33574
answered Sep 9 at 10:52
Jack M
17.6k33574
answered Sep 9 at 10:52
Jack M
17.6k33574
answered Sep 9 at 10:52
Jack M
17.6k33574
17.6k33574
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2910274%2fsum-of-all-powers-of-two%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
This is an odd question. Did this come from a course? If so, which course, and what kind of results/techniques have you covered recently? I ask, because it might affect which answer I'd give.
– Theo Bendit
Sep 9 at 1:59
You seem to have a good idea about approaching the problem, starting from the canonical binary expansion and splitting one or more higher powers to fill in gaps. Doing some modest size examples should illustrate how you might use induction or well-ordering to formally package a proof.
– hardmath
Sep 9 at 2:09
1
Bijective numeration.
– user202729
Sep 9 at 13:41