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

  • Thread starter Thread starter Dank2
  • Start date Start date
  • Tags Tags
    Induction Proof
AI Thread Summary
The discussion focuses on proving that every natural number can be represented in binary form using the equation n=i=0n∑ ai2i. Participants highlight the importance of correctly structuring the induction proof, emphasizing that the summation should not extend to n+1 and that the assumption of k being equal to n is flawed. They suggest using strong induction, where the proof assumes the statement holds for all natural numbers up to n, to establish its validity for n+1. Additionally, the conversation addresses the challenges of handling both even and odd numbers in the proof, recommending the use of the largest power of two less than n+1 to facilitate the argument. Overall, the thread provides insights into the nuances of mathematical induction and binary representation.
Dank2
Messages
213
Reaction score
4
<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=0n∑ ai2i

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

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

n+1=i=0n+1∑ ai2i
(i=0n∑ ai2i)+1=i=0n+1∑ ai2i

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

i know that 2n+1>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.
 
Last edited by a moderator:
Physics news on Phys.org
Dank2 said:
i know that 2n+1>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.
 
Last edited:
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.
Dank2 said:
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.

Dank2 said:
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.
 
FactChecker said:
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##.
 
Dank2 said:
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.
 
Dank2 said:
n+1=i=0n+1∑ ai2i
(i=0n∑ ai2i)+1=i=0n+1∑ ai2i
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##.
 
  • Like
Likes FactChecker
I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
Back
Top