Claim: every natural number n can be uniquely expressed in the form(adsbygoogle = window.adsbygoogle || []).push({});

n = 2^{jo}+ 2^{j1}+ 2^{j2}+...+ 2^{jm}

where m≥0 and 0≤jo<j1<j2<...<jm.

===========================

So I think we need to prove two things: (i) existence and (ii) uniqueness.

My idea is to prove existence first by mathematical induction, and after that prove uniqueness.

Base case:(n=1)

1=2^{0}(jo=0, m=0)

So the claim is true for n=1

Induction hypothesis: Assume the claim is true for n=k, k≥1

i.e. k = 2^{jo}+ 2^{j1}+ 2^{j2}+...+ 2^{jm}

where m≥0 and 0≤jo<j1<j2<...<jm.

With this, we need to prove that k+1=2^{to}+ 2^{t1}+ 2^{t2}+...+ 2^{tp}

where p≥0 and 0≤to<t1<t2<...<tp. (where p is not necessarily equal to m)

And now I am stuck. How can I prove that n=k+1 is true using the induction hypothesis? Notice that adding 2^{0}may not work because it is possible that jo=0, and now I feel hopeless...

Any help is much appreciated!:)

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Every natural number is sum of powers of 2

Loading...

Similar Threads - Every natural number | Date |
---|---|

I Is there a ket to correspond to every bra? | Jan 14, 2018 |

B Why does every subfield of Complex number have a copy of Q? | Jun 11, 2017 |

I Existence of spanning set for every vector space | Jan 29, 2017 |

I Proof that every basis has the same cardinality | Oct 6, 2016 |

Prove that every natural number is either odd or even | Mar 15, 2010 |

**Physics Forums - The Fusion of Science and Community**