induction

Printable View

August 27th 2007, 03:56 AM
ksssudhanva

induction

Hi,
can any one give me proof for mathematical induction?
August 27th 2007, 04:46 AM
TKHunny

Hmmm...That's a tough one. What do you mean? Can it be proven that Mathematical Induction works or is valid? The fundamentals lie in the logic. Do you mean just any old proof using Mathematical Induction? It may help if you would provide the actual wording of an actual problem statement. If this is a personal exploration, you're going to have to get substantially more clear.
August 27th 2007, 07:00 PM
kezman

The principle of mathematical induction is usually stated as an axiom of the natural numbers. However, it can be proved in some logical systems. For instance, it can be proved if one assumes:

The set of natural numbers is well-ordered.
Every natural number is either zero, or n+1 for some natural number n.
For any natural number n, n+1 is greater than n.
To derive simple induction from these axioms, we must show that if P(n) is some proposition predicated of n, and if:

P(0) holds and
whenever P(k) is true then P(k+1) is also true
then P(n) holds for all n.
August 28th 2007, 12:47 AM
ksssudhanva

induction

I mean how can you say the method of mathematical induction is true.
August 28th 2007, 07:06 AM
ThePerfectHacker

Quote:

Originally Posted by ksssudhanva

I mean how can you say the method of mathematical induction is true.

Well-Ordering Principle: Let $S$ be a non-empty set of natural numbers. Then $S$ has a smallest element!

Induction: Let $S$ be a set. Given $0 \in S$ and that if $n\in S\implies n+1\in S$ . Then $S=\mathbb{N}$ .

Proof: Let $T = \{ x\in \mathbb{N} | x\not \in S \}$ . Our goal is to show that $T$ is an empty set. Now assume that $T$ is non-empty. By the Well-Ordering Principle there exists a minimial element $a\in T$ . Now $a\not = 0$ since $0\in S$ . So $a\geq 1$ . That means it has a predecessor $a-1$ . Since $a-1<a$ it must and $a$ is minimal it means $(a-1)\in S$ . But then $(a-1)+1 = a\in S$ . A contradiction! Thus, $T$ must be empty. Q.E.D.