0

Show for any integer $k \geq 1$ can be uniquely expressed as $k = 2^x + i2^{x+1}$ for $i,x \geq 0$ and $i,x \in \mathbb{N}$

My attempt was to prove it inductively: $k = 1$, true assume true for $k = n$ i.e. $n = 2^x + i2^{x+1}$ then we know $k+1$ is either odd or even, say $k+1 = 2n = 2(2^x + i2^{x+1}) = 2^{x+1} + i2^{x+2}$ hence true for even $k+1$, now for odd $k+1 = 2n+1 = 2^{x+1} + i2^{x+2} + 2^0 $

I'm not really sure what to do about the "$2^0$" term and/or how to prove the uniqueness.

This is for a basic course so please avoid complex solutions if possible

thank you

Bruce Zheng
  • 1,039
  • 5
  • 11
Lekx33
  • 1
  • As this is your first post, I'm going to give some advice. (1) Try to write in complete sentences. {Example: after "$k = 1$, true" place a period}. (2) Use blank space {Example: before "assume true for $k = n$", start a new paragraph}. You can edit your posting to clean these things up. On the more technical front, when you assume that the statement is true for $k = n$, you write "i.e., $n = 2^x + i 2^{x+1}$," but that's not the statement you're trying to prove. The statement you're trying to prove is that there exist SOME non-negative integers $x$ and $i$ with $n = 2^x + i2^{x+1}$. – John Hughes Oct 17 '14 at 16:42
  • This seems inspired by this recent answer. Is it? – Did Oct 17 '14 at 17:08
  • @Did yes it is why? – Lekx33 Oct 17 '14 at 18:50
  • Why what? If indeed it is, you might have mentioned it, this is called giving one's sources. Failing to do so is lowly regarded in maths circles. (Additionally the question is already explicitely answered over there, so much so that I wonder why you asked this.) – Did Oct 17 '14 at 19:36
  • "This is for a basic course" Are you user @Jonx12? – Did Oct 17 '14 at 19:39

1 Answers1

0

Begin by writing $k=2^sm$, where $m$ is odd and $s\ge 0$. If $s=0$ then $k$ is odd, and we can uniquely write $k=1+2i$ for some $i\ge 0$, i.e. $k=2^0+i2^1$. If $s>0$ then we use our proof on odd numbers to uniquely write $m=1+2i$. Now $k=2^s(1+2i)=2^s+i2^{s+1}$. This must be unique since $s$ is the highest power of $2$ that divides $k$ (taking both sides mod $2^s$ and again mod $2^{s+1}$ shows this).

vadim123
  • 82,796