Is the proof to my statement correct?

The Student

Junior Member
Joined
Apr 25, 2012
Messages
241
If J is a subset of N (the natural numbers including 0)

1) 5 is an element of J,

2) If p is an element of J, then p5 + 5 is all positive multiples of 5

Then J = p5 + 5

The check that 1 is an element of J: 5 = 1(5) = 5

Here is p as an element of J: 5(p+1) = 5(p+1)

Then 5(p+1) = p5+5, and therefore J + p5+5

Is there anything else that I need to add?

Is there anthing that I did not need?

OOPS, I HAD TO EDIT. I HAD TO SWITCH A COUPLE THINGS, SO THIS POST HAS CHANGED SINCE 10 MINUTES AGO WHEN I POSTED IT.
 
Last edited:
Please give the exact problem statement rather than your summary.

Then provide a statement of the proposition to be proved.

I totally made the whole thing up from the idea of induction.

Could this be a problem statement: Prove that J is the set of all positive integers that are multiples of 5?

Could this be the statement: IF J is a subset of N (natural numbers including 0), and p is an element of J, and, if 5 is an element of J then 5(p+1) is an element of J THEN J is the set of all positive integers that are multiples of 5.

Does this work? Is this an example of induction?
 
Why are you trying to do 12 things all at once? Please stop confusing yourself.

IF J is a subset of N (natural numbers including 0), and p is an element of J, and, if 5 is an element of J then 5(p+1) is an element of J THEN J is the set of all positive integers that are multiples of 5.

No one can make sense of this.

IF J is a subset of N (natural numbers including 0)

Why do we care? How do we know?

and p is an element of J

Why do we care?

and, if 5 is an element of J

Why do we care? Why not, if 25 is an element of J. Are you sure 12 isn't in there?

then 5(p+1) is an element of J

Who says? PROVE it! This is an often-tried, but never effective method known as hand-waving - or maybe a magic wand.

J is the set of all positive integers that are multiples of 5.

Absolutely not.

1) Why did we need zero? Your last statement seems to ignore it.
2) You have suggested, rather weakly, that J contains a bunch of multiples of 5. You have not proven that J has ALL multiples of 5.
 
If J is a subset of N (the natural numbers including 0)

1) 5 is an element of J,

2) If p is an element of J, then p5 + 5 is all positive multiples of 5j
What does this mean? You appear to be simply defining "p5+ 5". So far all you have said about J is that "5 is an element of J". J= {5} satisfies that.

Do you mean "if p is an element of J, then p+ 5 is also an element of J"?

Then J = p5 + 5

The check that 1 is an element of J: 5 = 1(5) = 5
which says NOTHING about "1" being a member of J- in fact, it is not true.
You see to be confusing J (which I think you mean to be multiples of 5) with the set of numbers, k, so that p= 5k for p in J.

Here is p as an element of J: 5(p+1) = 5(p+1)

Then 5(p+1) = p5+5, and therefore J + p5+5

Is there anything else that I need to add?

Is there anthing that I did not need?

OOPS, I HAD TO EDIT. I HAD TO SWITCH A COUPLE THINGS, SO THIS POST HAS CHANGED SINCE 10 MINUTES AGO WHEN I POSTED IT.
 
Last edited:
This is not a good problem because:

(1) Early on you said that the form of induction you were given starts with proving a proposition is true for 1. If you are dealing with propositions that include zero, you either need a different form of induction (one that starts with 0) or your proposition needs to be formulated in terms of
(x - 1) so that if x = 1 then (x - 1) = 0. I explained this in my last post to your first thread.

(2) You have not said what the defining properties of J are so how in the world can you tell whether it includes all positive numbers that are evenly divisible by 5? If you want to think about induction in terms of set theory (which I personally do not feel is the most intuitive way to think about mathematical induction, but it is a rigorous way favored by mathematicians for the last hundred years), the set J must be the set of all natural numbers that have some specific property Q. Your object then is to prove that the set J = the set N, which means that all natural numbers have property Q. In other words, the object is NOT to show that the members of J have property Q because they necessarily do so by the definition of J; the object is to prove that every natural number has property Q by showing that J = N.

(3) You cannot prove that every natural number is an even multiple of 5 because it is false. 3 is not an even multiple of 5, nor are 13, 17, 49, or an infinite number of other natural numbers.

(4) Furthermore, a proof that something you have implicitly defined as true is true is completely trivial and does not require mathematical induction to prove. To get this concept, you need to prove a true property of natural numbers that is not part of the definition of natural numbers

Here is what I suggest. You get your book and find one problem that requires you to prove that some property is true of the natural numbers. That will be Q. I may have a little time tomorrow morning to look at your work, but I have meetings from mid-morning to mid-afternoon so I may not be able to do anything until halfway through the afternoon. In any case, I'd like you to give the problem statement word for word and then I'd like you to do the following.

Using the variable name x, write down what property the problem is asking you to demonstrate is true for every natural number. The statement should look something like

Prove that for every natural number x, x has property Q.

Property Q should be defined in math notation using x, not English.

The first line of the proof should say

Let J be the subset of N that contains every natural number x which has property Q.

With that definition, we do not have to worry that J contains tigers or asteroids or negative integers. If J contains anything, it contains just those natural numbers with property Q, and it contains all of them (if there are any).

Then prove that 1 has property Q. This will probably be a very simple proof involving basic arithmetic. The next to last line of this part of the proof should be the definition of property Q with 1 substituting for every x.

The next five lines of the proof will be

\(\displaystyle So\ 1 \in J.\)

\(\displaystyle Let\ k = an\ arbitrary\ member\ of\ J.\) How do you know J has any members?

\(\displaystyle So\ k\ is\ a\ natural\ number.\) Why is this true?

\(\displaystyle So\ (k + 1)\ is\ a\ natural\ number.\) Why is this true? Does this prove that (k + 1) is a member of J.

\(\displaystyle And\ ****\) The asterisks will be the definition of property Q with k substituting for every x. Why is this true?

Then if you can, using the preceding line as the basis for your proof, prove that (k + 1) has property Q.

If you cannot do this last step, someone will help you through it. If you know Proclus's method for finding proofs, it can be very helpful in finding a proof by mathematical induction. At the latest I shall be back on line by 3 East Coast time on Tuesday.

Busy week for me (moving)

I am going to try to answer your questions that you wrote in blue.

How do you know J has any members? We know J has at one member namely 1 because this information is given.

Why is this true? It is true because it is given that J contains at least {1} and any other natural number, and k will be an arbitrary member of J.

Why is this true? Does this prove that (k + 1) is a member of J. This is true because the given information tells us that both k and 1 are natural numbers, so their sum will also be a natural number. This does not yet prove that k + 1 is a member of J until it is used in the operation and shows that it has the same properties as the k and the 1 do (I think).

The asterisks will be the definition of property Q with k substituting for every x. Why is this true? tIt is true because we showed that plugging in the natural numer 1 has property Q, and when we plugged in k the same way, the result was akin to the natural number 1.




 
Busy week for me (moving)

I am going to try to answer your questions that you wrote in blue.

How do you know J has any members? We know J has at one member namely 1 because this information is given.

Where is that given? Your first statement was that 5 was in J, not 1.

Why is this true? It is true because it is given that J contains at least {1} and any other natural number, and k will be an arbitrary member of J.

Again, you see to be confusing J, which contains multiples of 5, with the set of k such that 5k is in J.

Why is this true? Does this prove that (k + 1) is a member of J. This is true because the given information tells us that both k and 1 are natural numbers, so their sum will also be a natural number. This does not yet prove that k + 1 is a member of J until it is used in the operation and shows that it has the same properties as the k and the 1 do (I think).

The asterisks will be the definition of property Q with k substituting for every x. Why is this true? tIt is true because we showed that plugging in the natural numer 1 has property Q, and when we plugged in k the same way, the result was akin to the natural number 1.

What you appear to be doing is using induction to prove "If 5 is in J and whenever p is in J, p+ 5 is also in j, then the set, K, of all k such that 5k is in J, is the set of all positive integers". (Note that 0 is not in either of those sets.)
 
Last edited:

Where is that given? Your first statement was that 5 was in J, not 1.


Again, you see to be confusing J, which contains multiples of 5, with the set of k such that 5k is in J.


What you appear to be doing is using induction to prove "If 5 is in J and whenever p is in J, p+ 5 is also in j, then the set, K, of all k such that 5k is in J, is the set of all positive integers". (Note that 0 is not in either of those sets.)

I meant for my answers to be generic and not specific to the one that I posted.
 
Student

I hope your move was successful. You did not quite do what I asked, which was to pick a well formed problem and do certain things with it. As was explained, the problem you made up had some problems with it, and it is impossible to teach or learn from a defective problem.

Here is what I propose. I shall give you a problem below. I shall ask you to do one step at a time, and I shall also ask questions about just that one step. Furthermore, we shall solve the problem by induction in TWO different ways, the pre-1830 intuitive way and the modern more rigorous way. Does that sound like a plan to you?

Here is the problem:

Prove that:

\(\displaystyle For\ every\ natural\ number\ x, \displaystyle \sum_{i=1}^x2^i = 2^{x+1} - 2.\)

ALL I want you to do first is to prove that the statement is indeed true if x = 1. The proof should use nothing but the basic operations of arithmetic and facts about specific numbers. For example 2^3 = 8. Notice that this step in the old-fashioned way of doing induction does not mention sets at all.

I will try the modern version.

1. If J is a subset of N (the natural number set)

2. And 1 is an element of S

3. And x is an element of J only if x+1 is an element of J

Then J=N


If 1 is an element of J, then 2^(1+1) - 2 = 2


How do you know J has any members?
We know J has at least one member, namely 1. And because 1 works the way that a natural number would work in this equation and we are given that J is a subset of the natural numbers, it must have property P. And, we do not know yet if k is a member of J.

If k is an element of J, then ... = 2^(k+1) - 2 *(I know that we have to show this, but I don't know why)*

Why is this true?
It is true because we let k be an element of J, and from the last example 1 is shown to be a
member of J, or in other words it has property P *(I am not entirey sure what property means)*.


Why is this true? Does this prove that (k + 1) is a member of J. It is true because when two natural numbers are added together, they equal another natural number. I don't think it is proven until we show the work where k+1 even though we know k+1 must be a natural number with property P. The following work shows this:

... = 2^((k+1)+1) - 2

*I am not sure if I have to do anything more with the above work.*
 
Here is the deal. If you want me to try to help you, please do as I ask. If you do not feel that I can be of help to you, please let me know to stop reading your posts, and I shall never bother you again.

If you are going to forward with me, I'd like you, without any reference to sets or anything except basic arithmetic, to PROVE

\(\displaystyle If\ x = 1, \displaystyle \sum_{i=1}^x2^i = 2^{(x+1)} - 2.\)

It is not at all hard to prove, and it requires no reference to sets at all.

I am not very knowledgable with proofs, and I have been trying to find information about Proclus's method for finding proofs, but I just can't find it anywhere on the internet.

All of what I typed is what I thought you were asking of me. I think I know what you want now. I think that you want me to show the equation when x=1. I did not know that this is a proper proof because I thought I had to show that 1 had property P first. So, this is my work now:

\(\displaystyle If\ x = 1, \displaystyle \sum_{i=1}^12^i = 2^{(1+1)} - 2.\) = 2^2-2 = 4-2 = 2
 
Now we are getting somewhere. Let's forget about Proclus for a moment because his method is not a method of proof; rather it is a method for finding proofs that SOMETIMES works.

In the example that we are using, the property P that we are attempting to prove true for the natural numbers is:

\(\displaystyle \displaystyle \sum_{i=1}^x2^i = 2^{(x+1)} - 2.\)

That is an example of a property that can be expressed as an equation. Some properties might be expressed in some other form, say as an inequation. But in the simplest case to grasp, the property is expressed as an equation.

So, does property P in this case mean that a certain element can be used in an equation? Does it mean anything else than that?

The way that you show that 1 has that property is to prove that when you substitute 1 into the equation, the equation is true.

Why do we have to show this property?

I SUSPECT that you got half the proof that 1 has the property in question, but now I am going to get a little bit formal and restate this HALF of half the proof. I repeat, I suspect that this was what was in your mind, but putting it down in excruciating detail will ensure that you and I are thinking along the same lines.

\(\displaystyle If\ x = 1, 2^{(x+1)} - 2 = 2^{(1 + 1)} - 2 = 2^2 - 2 = 4 - 2 = 2.\)

This is what you were thinking, right?

Yes

But this only proves half of what needs to be proved about 1.

\(\displaystyle If\ x = 1, \displaystyle \sum_{i=1}^x2^i =\ what?\).

The end of this half of the proof will be: \(\displaystyle \displaystyle \sum_{i=1}^12^i = 2^{(1 + 1)} - 2.\)

So, is the whole step 1 of this proof this: \(\displaystyle If\ x = 1, \displaystyle \sum_{i=1}^x2^i = \displaystyle \sum_{i=1}^12^i = 2^{(1 + 1)} - 2 = 2^2 - 2 = 4 - 2 = 2\).
 
Property to be proved true for the natural numbers:

\(\displaystyle If\ x\ is\ a\ natural\ number\, \displaystyle \sum_{i=1}^x2^i = 2^{(x+1)} - 2.\)

Being very detailed but old fashioned, the proof would look like this:

\(\displaystyle If\ x = 1, 2^{(x+1)} - 2 = 2^{(1+1)} - 2 = 2^2 - 2 = 4 - 2 = 2.\) This takes care of the right-hand sife of the equation.

I am assuming that you know what the large sigma means. Perhaps I should not have. It means sum. If you have any questions about what it means, please let me know.

\(\displaystyle If\ x = 1, \displaystyle \sum_{i=1}^x2^i = \sum_{i=1}^12^i = 2^1 = 2.\) This takes care of the left-hand side of the equation.

But the left-hand side = 2 = the right-hand side of the equation.

\(\displaystyle \displaystyle \sum_{i=1}^12^i = 2^{(1+1)} - 2.\) We have proved that 1 has the property in question because we have shown

that the equation is true if x is replaced by 1 everywhere that x occurs.

\(\displaystyle THUS, if\ x = 1, \displaystyle \sum_{(i=1)}^x2^i = 2^{(x+1)} - 2.\)

EDIT: THIS WOULD BE THE FIRST HALF OF THE PROOF.

Do you get the first half of the proof?

I understand some of it. But I still don't understand why we don't just start off by declaring that 1 is an element of N (the natural numbers), so that we don't have to show it? Or why isn't 1 just understood as an axiom that it is a natural number?

Is the whole point of this first part to show that 1 has a property of the natural numbers in order for the operation to be true? Also, do we need to show it so that we can eventually be able to use it as a natural number when we show it with k for when we get to the summation of 1 to k+1?
 
Let me ask some questions about your math background?

First, have you studied plane geometry and learned what a proof is and how to do one?

I only have grade 12 algebra and grade 12 calculus (here in Alberta it is the same as a fist year university calculus coarse). In both classes we worked a little bit with proofs, and I really liked it. They much more straightforward though. Currently I am getting prepared for first year honors calculus, and the professor that I am going to have in September was nice enough to direct me to all of the notes for the whole course. I have not yet come across anything in the first chapter that even mentions properties of numbers, so the first time ever knowing about them is by you. Also, the other parts of this first chapter that I am on does not seem to be giving me any issues ... yet.

Second, why did you ask this question on the calculus page? It is basically a question in arithmetic, what was frequently called in the 19th century "the higher arithmetic" but is studied today either as an introduction to abstract algebra or as the theory of numbers, which are courses that are generally studied in college by those planning to become math majors.

My goal is to get a Ph.D. in engineering physics going through the nanotechnology option. The student councillor told me that I will need this kind of math theory after I get my degree anyway, so anything that helps prepare me to do well in the future I want to take it. Also, I want to focus my spare time on studying when I am not in school.

Third, do you understand EXACTLY HOW we proved that \(\displaystyle If\ x = 1, \displaystyle \sum_{i=1}^x2^i = 2^{(x+1)} - 2.\)

Yes, I am pretty sure I understand it. I am just having difficulty putting my brain into the mode for this theoretical part of math.

There is no point in going on to the next step of the proof if you do not understand the first step.

PS It is getting late. I shall probably not post again today. But please respond, and I shall continue tomorrow morning.

I have one more question about this step. Like you mentioned earlier, 3 has a property of being an odd number. From what I gather now, in this instance, 1 is shown to have property P which is a property that shows that all other natural numbers have this property in common. So my question is: in this case, is property P definied as a property that shows that all other natural numbers have the same property? If so, this seems to me like it would be a very unique type of property compared to a property like odd or even.
 
Last edited:
I'll start with a review. Please ask a question ANYWHERE I have been unclear.

For right now, we are defining the natural numbers as 1, 2, 3, ....

A DEFINING property of the natural numbers is if k is a natural number, then (k + 1) is a natural number.

We are also going to assume as theorems all the BASIC facts of arithmetic. (Someone, probably Bourbaki, has proved them so we do not have to.)

A proof by mathematical induction involves PROVING that a specific property P is true for all of natural numbers. We are going to do the proof first by the old-fashioned way and then by the more modern way.

In a proof by mathematical induction, whether modern or old-fashioned, we cannot say that any natural number has property P until we have proved it (otherwise we would have a circular argument.)

Every such proof involves 2 steps. The first is to prove that 1, which IS a natural number by definition, has property P, which I have been stating in terms of an unknown natural number x. The way that we prove that 1 has property P is to show that the statement of property P is true when every x in the statement is replaced by 1. If the statement of property P is an equation, this means showing that the right-hand and left-hand sides of the equation have the same numeric value when 1 replaces x.

Why do we prove that 1 has property P when 1 is defined as a natural number? Because at the beginning of the proof, we have not proved that any natural number has property P, and obviously if 1 does not have property P, then it is false that all natural numbers have property P.

Enough generality.

The specific example of a property that we intend to prove is:

\(\displaystyle For\ every\ natural\ number\ x, \displaystyle \sum_{i=1}^x2^i = 2^{(x + 1)} - 2.\)

First step of the proof is:

\(\displaystyle \displaystyle \sum_{i=1}^12^i = 2^1 = 2.\) We evaluated the left-hand side of the equation for the case where x = 1.

\(\displaystyle 2^{(1+1)} - 2 = 2^2 - 2 = 4 - 2 = 2.\) We evaluated the right-hand side of the equation for the case where x = 1.

\(\displaystyle 2 = 2.\)

\(\displaystyle THUS\ \displaystyle \sum_{i=1}^12^i = 2^{(1+1)} - 2.\) The statement of the property is true when 1 replaces every x.

Notice that we proved this part of the statement using arithmetic. We were able to use the basic arithmetical properties of any specific numbers used in the GENERAL statement of property P (if there are any). in this example, that number is 2, and we used the basic arithmetical fact that 2^2 = 4. In addition, we were able to use the basic arithmetical facts about 1, such as 1 + 1 = 2, because this step in the proof is about 1 specifically. Note there is nothing circular. We did not assume that 1 has property P. We proved it.

This is the simple step so if you have any shred of confusion, we need to get rid of it before proceeding.

OK if you think about it, we actually proved two things:

\(\displaystyle 1\ has\ property\ P.\)

\(\displaystyle Consequently, there\ are\ one\ or\ more\ natural\ numbers\ with\ property\ P.\)

But we only proved that one number, namely 1, has property P. Where does the "or more" come from? If I tell you that I have one or more dollar bills in my wallet and we find that I have exactly one bill in my wallet when we look, I told the truth. "One or more" does not mean "more than one."

OK. We are now ready for step 2 of the proof. We arbitrarily choose one of the natural numbers, call it k, that has property P. We know that there is at least one to choose, namely 1, but we are hoping that there are more than one. But we cannot use any specific numeric fact about k. For example, we cannot say that k^2 = k. It is true that 1^2 = 1, but we are not limiting our choice to 1. Moreover, we do not know what specific number we are choosing. It may be 1 or it may not be. So there is no special numeric property that we can use about k. Here is what we can use:

Any of the basic arithmetic facts about EVERY natural number.
1 has property P (we just proved that).
If any specific number (say 2) comes up in the course of the proof, any arithmetical facts about that specific number.
k, which is a natural number and so is greater than or equal to 1, also has property P.

This last one is what drives people nuts. They say you have not yet proved that k has property P. Yes we have. We proved that there are one or more natural numbers with property P. And we chose k from among THOSE numbers. So it automatically has property P. We are not trying to prove that k has property P. It has that property by definition. We are going to prove that (k + 1) has property P. If you are with me to here, let's go to step 2 in our example. Here we go.

\(\displaystyle \displaystyle \sum_{i=1}^{(k+1)}2^i = 2^1 + ... 2^{(k+1)} = \left(\sum_{i=1}^k2^i\right) + 2^{(k+1)} = 2^{(k+1)} - 2 + 2^{(k+1)} = 2 * \left(2^{(k+1)}\right) - 2 = 2^{[(k+1)+1]} - 2.\)

\(\displaystyle In\ short, \displaystyle \sum_{i=1}^{(k+1)}2^i = 2^{[(k+1)+1]} - 2.\)

The statement of the property is true when (k + 1) replaces every x, which means that we have PROVED that (k+1) has property P.


Did you follow that? Any questions at all? I'll be gone for about 6 hours so you may not get a quick follow up.

I think I followed most of it.

I just have few questions. I am not entirely sure how the term property gets used in math. Are you saying that an algebraic equation is a property? If so, what is it a property of?

Also, I just want to get something straight here. Am I correct when I say that k+1 has property P only when k=1?
 
Property is just something that is true of something. Being warm-blooded is a property of being a mammal. Having the sum of the squares of the sides enclosing the right angle equal the square of the third side is a property of a right triangle in a plane.

Sometimes a property is best expressed as an equation, sometimes as an inequation, sometimes as something else entirely.

You are NOT correct in saying that (k+1) has property only when k = 1. That defeats the whole purpose of the proof. We choose k to be an arbitrary one of the natural numbers that have property P. It may be 1 or 749. We do not care. So no matter which number we pick, we have proved that the next number in succession after k also has property P.

In the 18th century, they would prove 1 has property P. Then they would prove that (k + 1) has property P given that k has property P. So, in conclusion, they would say therefore every natural number x has property P. The INTUITION behind this conclusion is that step one shows 1 has property P and then step two shows that (1 + 1) = 2 has property P, but then we can apply step two again so that (2 + 1) = 3 has property P, which means from step two that (3 + 1) = 4 has property P, and so on forever. The WHOLE point is that the proof that (k + 1) has property P does NOT depend on what specific number k is. It is ANY number with property P. That is why you can follow the chain from 1 to 2 to 3 to 4 to 5 forever.

So, if we wanted to show the sum when k=75, are we taking a small leap of faith without starting with k=1 and going through 2,3,4, ... 74?

Now I have a question for you. In the proof I gave in my previous post, where did I use the fact that k has the property P that we are using in this example?

In the summation expression that has the brackets.

Then if you have no further questions about the intuitive old-fashioned proof, we'll do the same proof in modern dress.
 
That sounds like a late 19th century mathematician. The 18th century mathematician would respond as follows. "I did start with 1. That was the first step, remember? So I could have chosen 1 for k in the second step and thus shown that 2 has property P. Of course in the second step, I said NOTHING about k being any specific number. So I could have picked 2 as k by doing the second step again, which means that 3 has property P. By keeping k unspecific, I was talking about ANY successor having property P, and I already showed that 1 has Property P, so the whole infinite row of dominoes just goes crashing down, one after another, as I do step two over and over again forever."

The late 19th century mathematician would say, "I need an axiom that says the whole infinite row of dominoes will fall." So Peano said, "OK let's assume that as an axiom." Now, what I learned from pka is that later, after Peano, someone found a simpler axiom in set theory to prove Peano's postulate as a theorem. So modern mathematicians say, "if you do not like Peano's postulate, invent a different mathematics." In fact, I personally believe that we accept Peano's postulate because it appeals to the same intuition that the 18th century mathematicians had, which is that a process has been defined, which starts with 1 and, by adding 1 each time, will eventually get to whatever number we are interested in, whether it is 74 or 74 billion. The whole key to that process is we prove something for 1 and then we prove that it applies to (k + 1) given it applies to k without making k specific. 1 is the first domino and down the rest fall.


Not quite. Let's review the DEFINITION of the summation notation.

\(\displaystyle If\ r = 1, \displaystyle \sum_{i=1}^ra_i = a_1.\)

\(\displaystyle If\ r\ is\ a\ natural\ number > 1, \displaystyle \sum_{i=1}^ra_1 = \left(\sum_{i = 1}^{r-1}a_i\right) + a_r.\)

Note that if k is a natural number, (k + 1) is a natural number > 1. And if r = k + 1, then r - 1 = k. So it is just definitional to say

\(\displaystyle \displaystyle \sum_{i=1}^{k+1}2^i = \left(\sum_{i=1}^k2^i\right) + 2^{(k+1)}.\)

It is the next step that is the killer. What justifies this?

\(\displaystyle \displaystyle \left(\sum_{i=1}^k2^i\right) + 2^{(k+1)} = 2^{(k+1)} - 2 + 2^{(k+1)}. \)

\(\displaystyle \displaystyle \left(\sum_{i=1}^k2^i\right) = 2^(k+1) - 2 \) is justified because the 1th 2 is added in the power, so we must minus off a 2 to keep the equation balanced.
 
\(\displaystyle \displaystyle \left(\sum_{i=1}^k2^i\right) = 2^{k+1} - 2 \) is justified because the 1th 2 is added in the power, so we must minus off a 2 to keep the equation balanced.

Couldn't you use the same argument to say that \(\displaystyle \sum_{i=1}^k 3^i= 3^{k+1}- 3\)?
 
What in the world does that mean? The 1th 2? There is no 2 in any power.

On the right hand of the equation is the SUM of 2^1 through 2^k. On the left is a PRODUCT of 2 times itself (k + 1) times minus 2.

I defy you to do algebra to get from one to the other. Show me how to add, subtract, multiply and divide with equal amounts on both sides of the equation to go from

\(\displaystyle 2^1 + 2^2 + ... 2^k = y\) to \(\displaystyle y = \left(2_{first\ time} * 2_{second\ time}\ *\ ... 2_{kth\ time} * 2_{(k+1)th\ time}\right) - 2.\)

If you cannot do that algebra, why did you say you had no questions about the proof?

I thought that I knew the answer, but now I definitely see the silly mistake that I made.

Now I admit it is very easy to prove it for a specific number. For example, if k = 4

\(\displaystyle 2^1 + 2^2 + 2^3 + 2^4 = 2 + 4 + 8 + 16 = 30 = 32 - 2 = 2^5 - 2 = 2^{(4+1)} - 2.\)

But we made a statement about a general k, not a specific number. What is the justification for that statement?

I will simplify the eqaution in question to this: \(\displaystyle \displaystyle \left(\sum_{i=1}^k2^i\right) = 2^{(k+1)} - 2.\) Now, my best guess is that the +1 in the 2's exponent that appears to come out of nowhere probably has something to do with the -2 that also comes out of nowhere. The only thing that makes sense to me is that the +1 must represent the first 2^1 in the series. Am I correct?
 
You must keep track of what is the property P that we are trying to prove and how far along we are in trying to prove it.

I still don't feel that I have a strong grasp of what property P is. For example, if I have an equation: 2x=10, is the property the equation? And does something that makes this equation true when filled in for x give it this property?

In this example, the property P that we are trying to prove is true for every natural number is:

\(\displaystyle For\ every\ natural\ number\ x, \displaystyle \sum_{i=1}^x2^i = 2^{(x + 1)} - 2.\)

At the beginning of the proof, we do not know that it is true for any number.

Our first step was to prove that \(\displaystyle \displaystyle \sum_{i=1}^12^i = 2^{(1 + 1)} - 2.\)

So that first step proved that 1 has property P AND that one or more natural numbers has property P.

We choose an ARBITRARY one of those natural numbers with propert P, calling the chosen number k.

That means k certainly has property P.

At this point, does k contain all natural numbers or does it just the number 1?

And that means \(\displaystyle \displaystyle \sum_{i=1}^k2^i = 2^{(k + 1)} - 2.\) This is the stepping stone that will be critical in the proof.

I am going to do the second step again, taking baby steps all along the way. Please make sure that you understand each step because the next proof you are going to do.

\(\displaystyle (k + 1)\ is\ a\ natural\ number.\) Because k and 1 are natural numbers, their sum is a natural number.

\(\displaystyle \displaystyle \sum_{i=1}^{k+1}2^i = \left(\sum_{i=1}^k2^i\right) + 2^{(k + 1)}.\) This just comes from the definition of summation.

\(\displaystyle \displaystyle \sum_{i=1}^{k+1}2^i = \left(2^{(k+1)} -2\right) + 2^{(k + 1)}.\) The sum in parentheses in the line above was

replaced by a different expression BECAUSE k has property P as we wrote down in the stepping stone statement. In a proof by mathematical induction, the fact that k has property P is always a crucial element in the proof that (k + 1) has property P.

\(\displaystyle \displaystyle \sum_{i=1}^{k+1}2^i = 2^{(k + 1)} + 2^{(k+1)} - 2.\) Commutative property of natural numbers.

\(\displaystyle \displaystyle \sum_{i=1}^{k+1}2^i = (2 * 2^{(k+1)}) - 2.\) Because (a + a) - 2 = 2a - 2.

\(\displaystyle \displaystyle \sum_{i=1}^{k+1}2^i = 2^{[(k + 1)+1]} - 2.\) Law of exponents.

But notice: we have just proved that the natural number (k + 1) has property P. (k + 1) has replaced x everywhere in the statement of the property.

We prove 1 has property P, which means that one or more natural numbers has property P.

We choose an arbitrary one of those natural numbers with property P.

That means (k + 1) is a natural number.

And we use the P property of k to prove that (k + 1) also has property P.

That gives us the falling row of dominoes. Do you get it now? Is it making any sense?

Surprisingly, even though I don't understand the beginning regarding what property P actually is and whether or not k contains numbers other than 1, I do see how k+1 is true and I also understand the operations of the formula that show how x is replaced by k+1

EDIT: When you are first learning how to do prrofs by mathematical induction, it may help to write down the statement of the property in four versions

one in x, the completely general version,

one where 1 replaces every x, which is what is to be proved in the first step of the proof,

one where k replaces every x, which is your stepping stone and is a given known to be true once the first step is done,

and one where (k + 1) replaces every x, which is what is to be proved in the second step of the proof.

Make sure you understand why the stepping stone version in k is true.
 
You do not have a CONCRETE idea because we want to generalize. In the example I gave, the property P is stated in the form of an equation:

\(\displaystyle a\ property\ of\ every\ natural\ number\ x\ is\ that\ \displaystyle \sum_{i=1}^x2^i = 2^{(x+1)} - 2.\)

U has property P if P is a true statement about U, whatever U is.

Perfect!!!, I now totally understand what is meant when a number is said to have a property or not have one.

A property of tigers is that they have stripes; that is a true statement about tigers. A property of stars is that they are hot; that is a true statement about stars. A property of natural numbers is that they are ordered; that is a true statement about natural numbers that is neither an equation nor an inequation. A property of me is that I live in the US; that is a true statement about me. Notice that not one of those properties is stated using a mathematical equation. Some properties about numbers are stated as mathematical equations or as mathematical inequations; some are not.

At its basic level, a proof by mathematical induction is a proof that every natural number shares a specific property that is not a defining property of the natural numbers. Each proof relates to a different property.

But, if induction says that all natural numbers has property P in certain examples, then shouldn't those certain examples be defining properties of the natural numbers?

Let's consider your example of 2x = 10. That is a property of the number 5. But it is not a property of every natural number
because, for example, it is NOT true that 2 * 4 = 10.

The concept of a property is not a hard concept, but it is a very general one. If the phrase "W has property P" bothers you, just substitute "P is a truth about W."


k is a natural number, not a set. So k does not contain anything.

Oops, I meant to ask: Can k represent anything but 1?, but now I don't think that's the point.

We intend to prove that P (whatever it is) is a property (a truth) for every natural number. Before we prove it, however, we do not know whether it is a truth. For example I could say "A property of every natural number x is that x^2 < 1." That is not true. That is not a property of ANY natural number. I can EXPRESS a falsity even though it is false.

So, to clarify, a proof by mathematical induction proves that a statement of a PROPOSED PROPERTY, P, is true for every natural number and so really is a PROPERTY of every natural number. But when we start the proof, we do not know whether ANY natural number has property P. I may have totally screwed this up by not making clear that at the start we are taking about a PROPOSED property of every natural number, which has not yet been shown to be a property of ANY natural number.

Trust me, it is not you. I have looked at so many examples and explanations of induction, and none of them helped. You are definitely helping me. If you are not a professor already, I think you would make a good one because you sure have the patients for it : )

Such a proof has two major steps. First we prove that P is true for 1, meaning 1 has property P. Now that is a CRITICAL logical step because, if P is not true for 1, it is certainly NOT true for EVERY natural number, and so P is certainly NOT a property of every natural number. However important logically this first step may be, it is usually fairly simple to do, often involving nothing but basic arithmetic.

Now there is an additional subtle consequence from this first step. We now know that P is a property of at least one natural number, namely 1, but of course it MAY be true of others. (In fact, we are hoping that it is true for an infinite number.) To put it another way, we have now proved that one or more natural numbers have property P.

So, in the second major step of the proof, we show that the natural number (k + 1) has property P given that k is any one of the unknown number of natural numbers with property P. So in the course of this second major step, we may use the fact that k is a natural number with property P because we picked k from natural numbers which have property P. If I ask you to pick at random a ball out of an urn containing only balls that are red, how likely is that you pick a red ball? Does it make any difference whether there is 1 ball or 10 balls or 100 balls in the urn, so long as there is AT LEAST one ball in the urn? So once we have proved that the natural number 1 is in the urn of natural numbers with property P, we know that the urn is not empty, and, for the second step of the proof, we pick any number from the urn and call it k.

This second major step is no more important logically than the first step, but it is frequently much harder.

The old-fashioned intuitive form of a proof by mathematical induction would complete steps 1 and 2 and then say in the very last line: "Therefore, every natural number has property P." Do you understand the intuition behind that last line?

I think so. Is it because we showed that k+1 is an element of the natural numbers where k represents 1? The answer to k+1 must be a natural number.

if you do, we can go in either of two different directions. We can take this example and dress it up in set theory to make it more rigorous, and then you can do a second example with me looking over your shoulder. Or you can do the second example the old-fashioned way, and then I'll show you how to dress up any such proof in set theory. I should say that I would bet most mathematicians use the old-fashioned method when they are just working and only dress it up when publishing. The dressing up is pretty mechanical because it just adds a few lines to the old-fashioned method. Tell me which direction comes next, but only if you fully understand the example given for the old-fashioned method.

I guess I could try to understand the set theory method, and if it does not come to me much sooner than induction, then I will just have to let it go for now.
 
You've received extensive (and wonderful) assistance from our volunteers here.

You seem to want more, like "an easy way to GET this."

Ain't happening. The concept of mathematical induction takes a certain amount of mathematical maturity. Put all of the good stuff you've heard here into your brain. Let it sit a while. Bring it up, look it over, turn it around and look again, over and over again until it makes sense to you.

Either it will, and you can call yourself a "mathematician-in-training" or it won't...and you can think about some other direction for your life.
 
Top