# Thread: Strong Induction - Sum of Distinct Powers of 2

1. ## Strong Induction - Sum of Distinct Powers of 2

Question (21.15):

Prove, using strong induction that every natural number can be expressed as the sum of distinct powers of 2. For example (21 = 2^4 + 2^2 + 2^0)

I understand there is a base step, but where do I go from there?

Thanks!

2. 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 that IF it'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:

$\displaystyle X = x_0 2^0 + x_1 2^1 + x_2 2^2 + ... + x_n 2^n$

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,

$\displaystyle 21 = 1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0 * 2^3 + 1 * 2^4$

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 that IF 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.

3. Sidenote:

Let's count up like this, so you can see what I mean. We'll do it in the form of a table where I just write out what you times the powers of 2 by:

NUMBER 2^0 2^1 2^2 2^3
0 0 0 0 0
1 1 0 0 0
2 0 1 0 0
3 1 1 0 0
4 0 0 1 0
5 1 0 1 0
6 0 1 1 0
7 1 1 1 0
8 0 0 0 1

etc

I hope that makes it a bit clearer, but it's still probably worth thinking about.

4. Originally Posted by Fedex
In maths, you prove that it's true for the number 1 then you prove that IF it'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".
But isnt this called the weak induction?

To prove it using strong induction, we have to assume the result holds for all numbers than n, then establish the result for 'n'.

5. To prove it using strong induction, we have to assume the result holds for all numbers than n, then establish the result for 'n'.
Damn, you're right. Think you meant "less than n" too?

I made it needlessly more difficult than it needed to be, apparently.

Thanks, Iso. Sorry, Ccdelia.

6. ## Yes!

Yes that's awesome! - I appreciate the help!

7. You're welcome :-)

,

,

,

### content

Click on a term to search for related topics.