Register to reply

Type of Induction

by e(ho0n3
Tags: induction, type
Share this thread:
e(ho0n3
#1
Jul27-08, 07:41 PM
P: 1,367
What do you call this type of induction (if it even exists):

Let P(x) be some statement concerning the integer x. If

- P(m) is true, and
- P(k) is true implies P(k + 1) is true, where m ≤ k < n,

then P(x) is true for all integers x = m, ..., n.
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
n_bourbaki
#2
Jul27-08, 07:48 PM
P: 103
It's just induction.
e(ho0n3
#3
Jul27-08, 08:43 PM
P: 1,367
I've been googling around but I haven't found a single website that mentions this sort of induction. I'll take your word for it.

Werg22
#4
Jul27-08, 08:49 PM
P: 1,520
Type of Induction

The only two terms for induction I've ever heard about are finite induction and mathematical induction.
uart
#5
Jul27-08, 08:58 PM
Sci Advisor
P: 2,751
Quote Quote by e(ho0n3 View Post
I've been googling around but I haven't found a single website that mentions this sort of induction. I'll take your word for it.
In the context of mathematics it's just plain induction but if you're googling then obviously you'll do better to use the full name "mathematical induction" because outside of Math the term "induction" has lots of other applications.
e(ho0n3
#6
Jul27-08, 09:41 PM
P: 1,367
I didn't just google "induction". I tried "finite induction types" and variations thereof.
uart
#7
Jul27-08, 09:58 PM
Sci Advisor
P: 2,751
http://www.google.com.au/search?q=ma...ient=firefox-a
n_bourbaki
#8
Jul27-08, 11:19 PM
P: 103
In this sense of the word, there is essentially only one form of induction.

Whilst we may use the terms 'induction' and 'strong induction' for two different things they are entirely equivalent notions (i.e. each one implies the other), and your notion of induction in post 1 falls between the two. It is a simple exercise to show that your description is equivalent to ordinary induction.
HallsofIvy
#9
Jul28-08, 06:32 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,348
"Strong induction" asserts:

If P(1) is true and
whenever P(n) is true for all [itex]n\le k[/itex], then P(k+1) is true

Then P(n) is true for all P

It is "Strong" because the hypotheses are easier- you only have to show P(k+1) is true when P(n) is true for all [itex]n\le k[/itex] so you have "more information". It is easy to see that "strong induction" implies regular induction: if P(k+1) is true whenever P(k) is true then it is certainly the case that P(k+1) is true whenever P(n) is true for all n less than or equal to k.

The remarkable thing is that regular induction implies strong induction:

Suppose P(n) is a statement such that:
P(1) is true and
whenever P(n) is true for all n less than or equal to k, P(k+1) is true.

Let Q(n) be the statement "P(m) is true for all m less than or equal to n".

Q(1) is the statement "P(m) is true for all m less than or equal to 1". But the only natural number "less than or equal to 1" is 1 itself. Q(1) just says P(1) is true- and that's true.

Now suppose Q(k) is true. That means P(m) is true for all m less than or equal to k and so, by the induction hypothesis, P(k+1) is true. But since we already have that P(m) is true for all m less than or equal to k, we now know that P(m) is true for all k less than or equal to k+1: Q(k+1) is true. Therefore, by regular induction, Q(n) is true for all n. But Q(n) says P(m) is true for all m less than or equal to n. If Q(n) is true for all n, then P(n) is true for all n.

The statement given in the first post looks like "strong" induction restricted to n greater than or equal to m. As everyone else has said, it is equivalent (as long as n is larger than or equal to m) to regular induction.
mrandersdk
#10
Jul28-08, 03:05 PM
P: 230
Quote Quote by Werg22 View Post
The only two terms for induction I've ever heard about are finite induction and mathematical induction.
there is also Transfinite Induction which is an extension to well-ordered sets

http://en.wikipedia.org/wiki/Transfinite_induction


Register to reply

Related Discussions
What type of Tea General Discussion 61
What type of... Introductory Physics Homework 5
Type of Course Academic Guidance 5
Type 1,2, & 3 Civilizations General Physics 7