Proof by Induction: Proving n=i=0n∑ ai2i

[Dank2]

<Moderator's note: Moved from a technical forum and thus no template.>

for every natural n there exists natural k.
and numbers={a0,a1,a2,...ak}∈{0,1}.

so that n=_i=0ⁿ∑ a_i2ⁱ

I will assume n=k, i know that if n is even then a₀ =0.

so if i assume it is true for n that is Even:

n+1=_i=0ⁿ⁺¹∑ a_i2ⁱ
(_i=0ⁿ∑ a_i2ⁱ)+1=_i=0ⁿ⁺¹∑ a_i2ⁱ

now from here i can try removing 1from left hand side, it's even then i can just put a₀=1
since a₀ was 0.

i know that 2ⁿ⁺¹>n+1, and therefore maybe i can try to remove it from right hand side:
and get that both sides are equal.

i'm having difficulty however, when n is uneven.

 

[FactChecker]

i know that 2ⁿ⁺¹>n+1, and therefore maybe i can try to remove it from right hand side:

That is a much higher power of two than you want to work with. You want to use the largest power of two, $2^k$, that is less than (EDIT: or equal to) n+1. Subtract that from n+1 and apply the assumption to the remainder.

 

[RPinPA]

This is not quite the correct form of an induction proof. Also, note that what this is saying is just "any natural number can be represented in binary with 0's and 1's".

For your proof then, you just need to show that you can add 1 in binary and the result represented in binary. The statement "there exists a k" just means "the binary representation has some finite length".

OK, now about the structure.

n=i=0n∑ ai2i

That's supposed to be a sum from 0 to k. You're just proving that n has a representation in k bits, for some k. For instance any number up to 31 can be represented with k = 5 or fewer bits.

I will assume n=k.

Why would you assume that? k in general will be a lot smaller than n. And the problem didn't say so, and if you prove that it only holds if k = n, then you haven't proved what you were supposed to prove. This assumption doesn't get you anywhere.

Recall the form of an induction proof.

1. Show it's true for n = 1. You didn't do this. How do you represent 1 as such a sum? What's k? How many terms do you need? What are they?

2. Assume it's true for n. Show it's true for n + 1.

OK, what you wrote can be part of this proof. It's easy to add 1 in binary if the number ends in 0, as you show. But your sums should not go to n. The thing you're proving has an unknown k in it, so leave the k in it.

Now your question is what to do when the number is odd? Well, I think I've given you plenty of hints on that, since I told you what mathematical operation is going on here.

 

[Dank2]

That is a much higher power of two than you want to work with. You want to use the largest power of two, $2^k$, that is less than n+1. Subtract that from n+1 and apply the assumption to the remainder.

I'm assuming it's true for $n$. but by subtracting greater power of $2k$ that is less than $n+1$, how do i get to $n$?
since $n-$$2^k$ > $1$ for example if $n =10, k=3$.
$n+1-2^3=3$.

 

[FactChecker]

I'm assuming it's true for $n$. but by subtracting greater power of $2k$ that is less than $n+1$, how do i get to $n$?
since $n-$$2^k$ > $1$ for example if $n =10, k=3$.
$n+1-2^3=3$.

You don't need to get to n, you just need to get to any natural number smaller than n+1. By subtracting any positive integer less than n+1, you get a smaller natural number. You can assume that you have proven the hypothesis for all natural numbers smaller than n+1. But subtracting a number too large will take you into the negative integers, for which nothing has been proven. That would be a mistake.

 

[vela]

n+1=_i=0ⁿ⁺¹∑ a_i2ⁱ
(_i=0ⁿ∑ a_i2ⁱ)+1=_i=0ⁿ⁺¹∑ a_i2ⁱ

You still have a problem for even $n$.

In your first line, you're saying
$$n+1 = \sum_{i=0}^{n+1} a_i 2^i,$$ which can work, though, as the others have pointed out, it doesn't really make sense to make the summation go to $n+1$. The problem here, though, is that this is what you're trying to prove. You should not be assuming this line is true, but deducing it.

In your next line, you claim
$$\left(\sum_{i=0}^n a_i 2^i\right) +1 = \sum_{i=0}^{n+1}a_i 2^i.$$ This doesn't work. You're saying the same $a$'s that work for $n+1$ also work for $n$. If you consider n=7, then its binary representation is 111, but the binary representation of n+1=8 is 1000. Clearly, the $a$'s are very different.

I think it would help you to use strong induction. Rather than assuming the statement is true for only $n$, you assume it's true for $0, 1, 2, \dots, n$. In other words, you assume there are binary representations for all natural numbers from 0 to $n$ and use this fact to show that there's one for $n+1$.