# Induction or Deduction?

1. Aug 28, 2006

### mtanti

Here it is, tell me who is wrong...

A definition of Induction and Deduction in a general science field:

Inductive approach- To understand something through obsevation with no prior knowledge and concluding at the end of your observations.

Deductive approach- To understand something through reasoning using prior knowledge and observing results of experiments using your hypothesis.

A definition of Inductive proof and Deductive proof in mathemetics:

Inductive proof- To proof a mathemetical statement by using an assumption and verifying that the assumption is correct.

Deductive proof- To proof a mathemetical statement by using a series of algebraic rules in order to change the form of one side of the equals sign into the other side and thereby proof an identity.

Now these are not quoted, just digested from what I understood in both subjects. Aren't they contradictions? If you use an assumption then it is a deductive approach whilst if you just follow a path using algebra and observation of how the form changes until you arrive to your answer then it is inductive. Am I wrong?

Or is it inductive because you have no pre defined knowledge and are observing the results given by an assumption whilst the other is deductive because you are using predefined mathematical proofs?

2. Aug 28, 2006

### mathman

Deduction (math and science) is the process of drawing conclusions from hypothesis through a series of logicallly valid steps.

Induction (science) is drawing conclusion based on a series of observations about many different cases of the situation under consideration.

Induction (math) is a completely different thing from that of science. It is a special tool which works like this. Prove something true for n=1. Assume it is true for any n and prove it true for n+1. (Prove meaning using deductive logic). Effectively what happened is that truth for n=1 implies truth for n=2 implies truth for n=3, etc.

3. Aug 28, 2006

### mtanti

Oh so induction in Maths has nothing to do with science?

Induction always confused me because just because you proof that something is true for n+1, what make you so sure that it is true for n as well?

Also the way you prove that n+1 is true is by making it equal to the assumption + 1. So what?

4. Aug 28, 2006

### HallsofIvy

Well, these are simply nonsense. Inductive Reasoning (not "inductive proof") involves reasoning from a number of special examples to a general principal- but it is never "proof".

"Deductive reasoning" involves reasoning from a general principal to a special case- but it does not necessarily have to be "algebraic" nor is it only used to prove "identities"!

5. Aug 28, 2006

### HallsofIvy

You prove (not "proof"- that's the noun) first that the statement is true for n= 1 so you know it is true for some n- and that's what you are using: if it is true for some n, then it is true for n+1.

I have no idea what you mean here. Making what equal to "the asssumption +1"??

6. Aug 28, 2006

### gnomedt

In more casual terms, induction is taking a finite number of observations and "inducing" a larger conclusion. Proof by induction is called "proof by induction" because it requires only two observations: that it is true for at least one number, and then if it's true for that one number, then it must be true for the next, and the next, and so on. As a more shaky example of inductive reasoning: "it looks like a duck, it quacks like a duck, it's a duck."

Deduction, on the other hand, is taking a general law and "deducing" lesser conclusions. For example, if we know that for any two numbers a and b, ab = ba, then 3*5 = 5*3. Deductive reasoning is always reliable; inductive reasoning isn't usually reliable, for obvious reasons.

Proof by induction requires two steps: first you must make sure that the statement to be proved is true for at least one number -- for our purposes, call it n0 (it doesn't have to be 0). Then, you show that if the statement holds for any number, then it's true for the next number. Only by combining these two steps is an inductive proof complete. Therefore, it must be true for every integer greater than n0.

Proof by induction, unlike most inductive reasoning, is always reliable. It's kind of a special case of inductive reasoning.

Last edited: Aug 28, 2006
7. Aug 28, 2006

### Edgardo

I think you misunderstand how proof by induction works. I try to explain:

Part A:
The crucial part is to show the step "S(n) -> S(n+1)". In this step we assume that a certain statement S is true for some number n (We write: S(n) is true). It is really important to understand that we only ASSUME that. We do NOT prove it.
Then we use this assumption and show that the statement S is also true for n+1.
In short: IF S(n) true, then we must show that S(n+1) true.

We did NOT prove that statement S is true for some number n, we just ASSUMED it and used it to show some other statement. It's just like saying: IF x>0, then 3*x>0.

Part B:
And now comes the second part that you have to understand. Suppose you have shown that from S(n) it follows S(n+1). Just do the following: show that your statement is true for n=1, that is S(1). After you've done that, what can you conclude?

Well, IF S(1) true, then S(2) is true. (This is because you have shown in Part A: IF S(n) true, then S(n+1) true).
Now, IF S(2) is true, S(3) is true. And so on....
You can climb up to any arbitrary n and show that statement S is true.
This is some sort of domino effect. If the first domino falls, the second does, the third does and so on.

Note: Usually, you first show Part B, that is you first plug in some value for n, for example n=1 and show that S(1) is true. If S(1) is not true, you know that the "first domino" does not fall.

Last edited: Aug 28, 2006
8. Aug 28, 2006

### mtanti

good explanation, however how do you prove that if S(n) is true then S(n+1) is also true? Thats the confusing part...

Like I said which perhaps was not clear... "Also the way you prove that n+1 is true is by making it equal to the assumption + 1. So what?" means that you prove S(n+1) is true by transforming it into S(n)+1. OK it won't be an actual +1 but S(n+1) must be expressed as a function of S(n), your assumption (perhaps I'm forgetting what comes next...). So what good will that do in order to prove that if S(n) is true then S(n+1) is also true?

9. Aug 28, 2006

### Hurkyl

Staff Emeritus
Derive some stuff.
Arrive at the conclusion that S(n+1) is true.

Here's a simple example.

Suppose I tell you that f(1) = 0, and that f(n + 1) always equals f(n). How would you prove that, for any integer n > 0, f(n) = 0?

Last edited: Aug 28, 2006
10. Aug 29, 2006

### mtanti

Well you see what is being done to the number in the function I guess, such as looking for a simplification which is f(n)=n-1

So how do you arrive at your conclusion that s(n+1) is true? You are basing your proof on an assumption after all...

11. Aug 29, 2006

### JonF

Oddly enough mathematical induction is actually a form of deduction. Part of the rigor of mathematics is conclusions follow from previously proven statements or axioms by necessity. This is not the case with scientific induction. I like the set approach to mathematical induction more because it seems to make more apparent the deductive nature of mathematical induction.

Let us say we have some statement, namely P(n). What we want to know is which n’s will make P(n) true. So let us consider the set of n that make P(n) true. We will call this set “S”. First we show that 1 is an element of S. Second we show if n is an element of S, then n+1 must also be an element of S. But, then the natural numbers must be a subset of S, according to the definition of the natural numbers. Thus the natural numbers satisfy P(n).

This might sound a bit sketchy so let’s follow the induction for awhile to see how it pans out.

We start by considering the set S of n’s that make P(n) true. We prove that 1 is an element of S. Then we prove if n is in S n+1 is in S*. So we know 1 is in S because that is the first thing we prove. But by * if 1 is in S, 2 must be in S also. But again by * if 2 is in S then 3 is there also. Yet again by * if 3 is in S then 4 is too. This process can be carried out indefinitely. Given any natural number, I can repeat this process some number of times and show that that number is in the set S.

12. Aug 29, 2006

### JonF

Why don’t we try mathematical induction on another statement and see if it helps.

Let P(n) be the statement: The sum of all the natural numbers from 1 to n is equal to n(n+1)/2

Let’s start by considering all the n’s that will make this statement true. We will call the set of these n’s S.

Claim: 1 is in S.
Proof: (1)(1+1)/2 = (1)(2)/2 = 2/2 = 1

Claim 2: if any natural number n is in S, n+1 is also in S
Proof: Let us assume that n is in S. That is the sum of all the natural numbers from 1 to n is equal to n(n+1)/2. Thus…

1+2+3+4+5+…+n+(n+1) =
n(n+1)/2 + (n+1) =
n(n+1)/2 + 2(n+1)/2 =
[n(n+1) + 2(n+1)]/2 =
[n^2 + n + 2n+2)]/2 =
[n^2 + 3n + 2)]/2 =
[(n+1)(n+2)]/2
Thus n+1 satisfies P(n)

Notice going from the first to the second line is justified by our assumption. We ASSUME that P(n) is true for n. That is the sum of all the natural numbers from 1 to n is equal to n(n+1)/2. And we use that to then prove n+1 is true, that is: The sum of all the natural numbers from 1 to n+1 is equal to (n+1)(n+1+1)/2

But by claim 1 and claim 2 we have now proven that the natural numbers are a subset of S by the definition of the natural numbers.

Last edited: Aug 29, 2006
13. Aug 29, 2006

### mtanti

OK OK, I've got the actual question now... Sorry but it's not easy to come up with the right question in maths...

---------------------------
Why is it that just because you manage to simplify P(n)+([n+1]th term) into P(n+1) mean that P(n) is true?
---------------------------

Is there a mathemathical reason for this or am I doubting reality and any kind of proof?

14. Aug 29, 2006

### Edgardo

After simplifying "P(n)+([n+1]th term) into P(n+1)" we have ONLY shown:
IF P(n) is true for a SINGLE n, then P(n+1) is also true.

This step does not prove that P(n) is true for ALL n!!!

Is that maybe the part that is confusing?

Last edited: Aug 29, 2006
15. Aug 29, 2006

### mtanti

No the part thats confusing is why is it that after simplifying "P(n)+([n+1]th term) into P(n+1)" you have proved that P(n+1) is true if P(n) is true. What makes you so sure?

16. Aug 29, 2006

### Hurkyl

Staff Emeritus
If you can't see how to prove it with mathematical induction, can you come up with some other way to prove it? (even if it's just an intuitive proof?)

also, f(n) = n-1 is wrong. (Since f(2) = 0)

Most proofs are based on an assumption -- you assume that the hypothesis of your postulate is true, and from that you derive the conclusion of your postulate.

or, more formally, when P is false, "P => Q" is true.

17. Aug 29, 2006

### Swapnil

I see your worry here. I think.

OK, so lets do this with the help of a similar example. Say your sitting on a chair one day just playing around with numbers when you, amazingly enough, "discovered" this relationship:

1 + 2 + 3 + ... n = n(n+1)/2

You were surprised. You checked if the above relationship is true for the numbers 1,2,3,4, and 5. But you know that you can't possibly check if this is true for ALL numbers! Life is too short for that.

You are wondering what to do, when you suddenly recall this beast called "mathematical induction." You are extremely happy and now you set to prove your relationship.

Left hand side: Duh! Obviosly the sum of all number from 1 to 1 is 1.
Right hand side: 1(1+1)/2 = 1
Marvelous! You proved that your relationship is true for n = 1.

Now for the hard part. You know that you have to prove that P(n) => P(n+1) (=> meaning implies) (meaning if P(n) is true then P(n+1) HAS TO BE TRUE). If you can do this, then since you relationship is true for n=1 it HAS TO BE TRUE for n=2 and since its true for n=2 it HAS TO BE TRUE for n=3 and since its true for n=3 ... and so on.

You are determined to prove that P(n) => P(n+1). You make the statement P(n) the relationship you found earlier i.e.

1 + 2 + 3 + ... n = n(n+1)/2 (Note that this WHOLE statement is your P(n) )

Now, just to be conservative, you write down P(n+1) as well i.e.

1 + 2 + 3 + ... + n + n+1 = (n+1)(n+1+1)/2 = (n+1)(n+2)/2

You know that you have to prove that P(n+1) LOGICALLT FOLLOWS from P(n). You look at P(n+1). The left hand side of P(n+1) looks just like P(n) except that it has an extra n+1 term. What you do? Your aim is to DERIVE P(n+1) FROM P(n). So you do what you think is best. You add the term n+1 to both sides of the satement P(n). You know that there is noting wrong with adding the same quantity to both sides of an equation. After you do that, your P(n) looks like the following

1 + 2 + 3 + ... n + (n+1) = n(n+1)/2 + (n+1)

Now, if only you could prove that
n(n+1)/2 + (n+1) = (n+1)(n+2)/2
then you would have successfully derived P(n+1) from P(n).

You go do the algebra and you successfully manage to transform the left hand side of the above equation (i.e. n(n+1)/2 + (n+1) ) into (n+1)(n+2)/2. You have proved that
n(n+1)/2 + (n+1) = (n+1)(n+2)/2
and thus P(n) => P(n+1)
(actually, P(n) and P(n=1) are "equal" but but I am not sure how the word "equal" applies to statements. "equavalent" is a better word)

... and the rest is history.

Last edited: Aug 29, 2006
18. Aug 29, 2006

### Swapnil

What you have written here is somewhat misleading. Its not that you are simplifing "P(n)+([n+1]th term)" into "P(n+1)." You are simplifying "P(n)" into "P(n+1)." It doesn't really makes sense to ADD "([n+1]th term)" to "P(n)" since you are adding the term n+1 to both sides of the statement P(n) and thus you are not changing P(n) in any way.

Hope this helps.

19. Aug 29, 2006

### Swapnil

Also, just for your information, mathematical induction can only be used to proved relationships which involve whole numbers. However, even though mathematical induction is somewhat limit, nevertheless, it an extremely useful "trick" in mathematics.

20. Aug 29, 2006

### WhyIsItSo

You guys are losing me. To pick on someone at random...
That seems like saying "10 Oranges is true". It doesn't make any sense. What am I missing?

21. Aug 29, 2006

### quasar987

S(n) represents a statement about whole numbers. For exemple, if we want to prove that

$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$,

S(n) represents the above equality. The statement S(9) is true means that the equality

$$\sum_{i=1}^9 i= \frac{9(9+1)}{2}$$

is true.

The principle of mathematical induction is based on the following logic:

If we can prove that S(n+1) is true based only on the assumption that S(n) is true, and if we can prove that S(1) is true, then it follows that S is true for any integer.

Why? Because we've shown that if S(1) is true, then, S(1+1)=S(2) is true. And this implies in its turn that S(2+1)=S(3) is true. etc.

22. Aug 29, 2006

### Swapnil

"The statement S(n) is true" means that the right hand side and the left hand side of S(n) are equal for any arbitrary value of n (in the proper domain that is).

What's wrong with saying, "Start with the hypothesis that S(n) is true"?

23. Aug 29, 2006

### gnomedt

In my opinion, the confusion here is in the notation S(N). S(N) isn't a typical function. S(N) is in fact more like a statement. But an example will illustrate the idea much better than vague statements like that.

In our example, S(N) means "The number N has the property that if you sum up the numbers (i.e. integers) from 1 to N, that sum will be equal to (N)(N+1)/2". In other words, S(N) is either yes or no, or true or false if you prefer. That's why we write it S(N) -- because whether or not S is true or false depends on N.

Proof by induction first shows that S(1) is true. That is to say the following: "The number N has the property that if you sum up the numbers from 1 to 1, that sum will be equal to (1)(1+1)/2". Well, that equality holds, because the sum is 1 and (1)(1+1)/2 = 2/2 = 1, so they're equal. Therefore, S(1) is true.

Now, the deal for proof by induction is that we must show is that if S(N) is true, then S(N+1) must also be true. What that means is that if:

"N has the property that the sum of numbers from 1 to N = (N)(N+1)/2"

then it must also be true that

"N+1 has the property that the sum of numbers from 1 to N+1 = (N+1)(N+2)/2".

A little algebra shows this to be true, algebra which I won't repeat here because it's been done above.

Then you get the domino effect also described above, and QED!

Last edited: Aug 29, 2006
24. Aug 30, 2006

### mtanti

Hello again, So if you can attain S(N+1) by expanding S(N) than the assumption was correct for some set of values? But why is that?

The real deal with the problem is that you proof is still based on an assumption... If you get S(N+1) from S(N) doesn't really mean anything because S(N) is just an assumption. OK so here is the master question:

Is it possible to attain S(N+1) from S(N) by expansion if S(N) is wrong?
Is it possible to not attain S(N+1) from S(N) by expansion if S(N) is correct?

Last edited: Aug 30, 2006
25. Aug 30, 2006

### Swapnil

I am not sure if you are understanding the logic behind mathematical induction. Your question doesn't make any sense.

I think you should read this discussion one more tme, because this question has been answered many times (in many different ways).
Let me try to explain one last time,
After you derive S(n+1) from S(n), you come up with the following conclusion: "IF S(n) is true, then S(n+1) is true" (let me call this (*) )
Yes, S(n) is still an assumption (that's why we have the qulifier IF).
BUT, for the base case we proved that S(1) is true. From (*) we can conclude that since S(1) is true therefore S(2) is true, then since S(2) is true, it follows from (*) that S(3) is also true, and so on till infinity.

I will answer this later. I gotta run.