Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2006-07-19 21:34:26

jackson6612
Member
Registered: 2006-07-19
Posts: 5

why mathematical induction works?

Hi

We need especially two things in order to proceed with mathematical induction. Steps 1 and 2 determine whether we can proceed or not. Steps 3 and 4 determine accuracy of formula.

1: Formula S(n) -- because without formula we have nothing to prove.

2: Proving formula at n=1 , here 1 is called starting point ( we don't always need to have n=1 as starting point, like in, n! > 2^n, we will start with n=4 because n!>2^n doesn't allow us to use n=1 as starting point ). This step is necessary because if S(n) is not true at n=1 ( or at any other particular starting point n, like n=3,5,6 etc ) then there's really no point in continuing. I think starting with n=1 ( like when formula allows us, formula n! > 2^n doesn't allow us to use n=1 )is convention. Right?

3: Assuming formula is true at n=k.

4: Proving formula at n=k+1. This step decides whether formula is correct or not.



I just came to know that I don't really understand why mathematical induction works. Please keep in mind while answering my questions that I'm going to be first year college student in next few months.


Suppose I just found these three formulae for the sum of n natural numbers (1+2+3+...+n) are:

n(n+1)/2,  n(n+1)n!/2,  n(n+1)2^(n-1)/2

As I mentioned before we need two things in order to proceed with mathematical induction.

1: Formula -- which we have.

2: Proving formula at n=1 ( if formula allows us - above formulae allow us to use n=1 as starting point )

All three of above formulae are correct at n=1; although I know two of them aren't correct but mathematical induction only needs to evaluate formula at n=1 and making sure it is correct at n=1.

3: In this step we assume above formulae are also correct at some n=k ( k can be any natural number, 50, 60, 70,110 etc ). This step doesn't make any sense to me. We are assuming what we are trying to prove so what's left there to prove.

4: In this step we evaluate above formulae at n=k+1. This step decides the accuracy of formula. But I don't see how.

So how will we know that one of above formulae is correct and other two are inaccurate?


Please don't give me those dominoes kind examples. Thank you


Sincerely,
Vijay

Offline

#2 2006-07-19 22:13:46

numen
Member
Registered: 2006-05-03
Posts: 115

Re: why mathematical induction works?

The point is that if you prove that if it is true for n=k, it is also true for n=k+1. If we end up with a statement which is true based on that assumption, it means that the assumption we made is true. If, however, we'd end up with a false statement as a result of that, our original assumption would be wrong.

You can look at it this way:

1) If x is true --> y is also true
2) If x is true --> y is false

1) If our assumption x is true, it leads to a statement y which is true. So our assumption must be correct.
2) If our assumption x is true, it leads to a statement y which is false. So our assumption cannot be correct.

Apply this to your problem. If what you are saying is true, two of those formulas should lead to a false statement, meaning that the assumption that it is a formula for the sum of natural numbers is false.


Bang postponed. Not big enough. Reboot.

Offline

#3 2006-07-20 01:53:47

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: why mathematical induction works?

1) If our assumption x is true, it leads to a statement y which is true. So our assumption must be correct.

Not true.  I'm going to assume that all even numbers are divisbile by 1.  Therefore, 2 must be even, since it's divisble by one.  I was lead to a correct statement, therefore my assumption must be true.

How about this one: Assume all odds are prime numbers.  3, 5, and 7 are all prime.  Therefore, the assumption must be correct.

2) If our assumption x is true, it leads to a statement y which is false. So our assumption cannot be correct.

This is correct logic.  Because if we assume something, then use logic we know is right, but reach a conclusion we already know is wrong, then either our assumption or logic is wrong.  We hope that our logic is right, so we blame the assumption for being wrong.

Here is how induction works.  First thing you do is the base case, lets call it a_0.  And you show that a_0 is true for whatever statement you are proving.

Now we don't assume anything.  Sort of.  Next thing we do is prove that if a_n is true, then it must be the case that a_n+1 is true.  Now whenever we do an if-then statement in logic, we always assume the if part is true.  So it is an assumption, but it's an assumption in an if-then statement, which is prefectly ok.

So if a_0 is true, and a_n being true means that a_n+1 is true, then it has to be the case that a_1 is true.  And if a_1 is true, then it has to be the case that a_2 is true.   And if a_2 is true... and so on.  And it will go for all the natural numbers.

Don't ask me why they just say assume a_n and then prove a_n+1.  To me, that's very confusing and misleading.  What we are really doing is proving the if statement, if a_n, then a_n+1.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#4 2006-07-20 03:52:13

numen
Member
Registered: 2006-05-03
Posts: 115

Re: why mathematical induction works?

Ricky: ok, perhaps I should've worded it correctly, would an equivalent statement make more sense?

Since; All odds are prime numbers <--/--> 3,5 and 7 are prime

Last edited by numen (2006-07-20 03:53:53)


Bang postponed. Not big enough. Reboot.

Offline

#5 2006-07-20 04:27:10

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: why mathematical induction works?

But if we assume a_n, as we do when we do induction, are you saying that a_n+1 is an equivalent statement?  It's not.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#6 2006-07-20 04:44:49

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: why mathematical induction works?

Jackson, here is a simple example.  We have a sequence of numbers:

{1, 2, 3, 4, ...}

To represent this sequence, we say:

We want to show that

for all natural numbers n.  So we use induction:


And that's our base case.  Now we want to prove:





And we're done.  We know that:


And in the same sense:

And this will continue on forever.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#7 2006-07-20 15:33:22

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: why mathematical induction works?

suppose any statement for 1,2,3,...,n is like this:
I I I ... I
if statement 1 is true can be expressed like this
I
and that when a statement is true, the proceding statement is also true can be expressed like this( Statement k is true, then Statement k+1 is true)
I I  => I I

then for n statements satisfying two conditions of induction:
I I I I I... I
I I I I I... I
I I I I I... I
I I I I I... I
I I I I I...I
...
I I I I I... I


X'(y-Xβ)=0

Offline

#8 2006-07-22 04:02:39

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: why mathematical induction works?

It's interesting that the induction is so foundamental, that it can't be proved or disproved using only non-induction methods. It's axiomatically true. It's the fifth of the Peano's axioms:
http://en.wikipedia.org/wiki/Peanos_axioms


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

Board footer

Powered by FluxBB