Okay, I think this is how you need to be thinking:

Induction works like dominos - you first knock down the first domino and each one knocks down the next one along and so on.

In maths, you prove that it's true for the number 1 then you prove thatIFit's true for a number, then it's true for the next number along. Then you say: "Ah, but it's true for 1, so it must be true for 2, which means it must work for 3, and 4, and 5, etc".

So:

"every natural number can be expressed as the sum of distinct powers of 2"

[By the way, if this WASN'T true, then binary wouldn't really work :-) ]

Step 1:

Now, let's prove it for n = 1.

1 can be written as 2^0. So that's that one done.

Step 2:

Let's look at a number X, which will ASSUME (we have no proof or anything, we're just going to say so) that it CAN be written as a sum of powers of 2.

So:

where any of these little x_n s can be either 0 or 1. 0 indicates that there is none of this power of two in the sum. 1 indicates there is. You need distinct powers, so none of these x_n s can be more than 1.

So to use your example,

Okay?

The next number after X must be X + 1.

X + 1 can be written as X + 2^0 so you just make sure that x_0 is turned into a 1.

If 2^0 is "taken" (i.e. x_0 is = 1) then that means that you have to gather the existing 2^0 and the new one together and make a 2^1 which you can add (so you would add a 2^1 and take away their 2^0 because you "used it up").

If you can't do that (if x_0 and x_1 are both = 1) then you add the 2^0 of yours to the 2^0 and the 2^1 already there to make a 2^2 ("using up the existing 2^0 and 2^1) and add that.

The point is: Those x_0, x_1, x_2, etc in that equation that I wrote that go all the way up to x_n: You just go along them until you find the first one that's a zero and turn it into a 1 and turn all the ones before it into a zero.

In that way, you'll have added 1 to the number and written X+1 as a sum of distinct powers of 2.

Phew. If you recognise binary, that will sound familiar.

Now we know thatIF X can be written as a sum of powers of 2 then so can X + 1.

Step 3:

We know it's true for 1, because proved it in step 1. So then we know that it must be true for 1 + 1 = 2.

But if it's true for 2 then it must be true for 2 + 1 = 3

But if it's true for 2 then it must be true for 3 + 1 = 4

But if it's true for 2 then it must be true for 4 + 1 = 5

etc etc

Congratulations, you've just proved it for all natural numbers.

I'm not sure if that makes sense - you might need to read it a few times.