My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree2Thanks
  • 1 Post By JeffM1
  • 1 Post By Country Boy
Reply
 
LinkBack Thread Tools Display Modes
July 14th, 2017, 11:15 AM   #1
Newbie
 
Joined: Apr 2017
From: Canada

Posts: 25
Thanks: 1

Mathematical Induction

I've got a question about mathematical induction.

Our first step is to prove that a given theorem holds for "n".

Then we prove that rule holds for "n+1"

Finally, we show that a rule holds for 1.

If the theorem withstands all of these steps, it means that it not only works for 1 but also all of the numbers above (n+1).

It would work for 1, 1+1=2, 2+1=3, 4 ... etc.

However, If our theorem deals with 0 or even negative integers, does the process above remain effective when dealing with negatives or do we need to alter the induction process to show that if theorem holds for "n", it must hold for "n-1"?

In other words, does induction ONLY tell us that the rule holds for all integers GREATER than 1?
Antoniomathgini is offline  
 
July 14th, 2017, 11:32 AM   #2
Senior Member
 
Joined: May 2016
From: USA

Posts: 785
Thanks: 312

You do not have the sequence of weak mathematical induction in the proper order.

We have a proposition about a natural number P(n). We want to prove P(n) is true for any n that is a natural number. If you can prove that directly you do not need mathematical induction.

Define the set of natural numbers for which P(n) is true as S.

At this point, S may be empty.

Prove that P(1) is true.

This also shows that S is NOT empty.

Now consider an arbitrary element of S called k. (we know that at least one such number exists because S is not empty.) Because k is an element of S, it is a natural number, equals or exceeds 1, and P(k) is true. Now prove that P(k+1) is true given those three facts.

The intuition is that it is true for 1 (by the first step) and (by the second step) it must be true for 2, but then it is true for 3, then 4, and so on forever.

You can use induction for proofs about natural numbers that equal or exceed some initial integer (which need not be positive). Suppose you want to prove that P(n) is true for any natural number > - 1. Restate P(n) as proposition Q(m) where n = m - 2. So when m = 1, n = - 1. Off you go.

You can also use induction for proofs about all integers. Restate P(n) as proposition Q(m) where n = m - 1. That will give you all the non-negative integers. Now prove that
P(n) and n > 0 proves P(-n).
Thanks from Antoniomathgini
JeffM1 is offline  
July 17th, 2017, 03:31 PM   #3
Senior Member
 
Joined: Oct 2009

Posts: 141
Thanks: 59

Quote:
Originally Posted by Antoniomathgini View Post
In other words, does induction ONLY tell us that the rule holds for all integers GREATER than 1?
Yes.

However, there are many ways to extend induction beyond the natural numbers. It is entirely possible to give an induction scheme that works for integers, rational numbers and even real numbers (even though I have yet to see them used in practice, especially for the reals).

For the integers, we could have the following scheme:
1) Prove the property holds for 0
2) Prove that if the property holds for n, then it holds for n+1
3) Prove that if the property holds for n, then it holds for n-1
Then the property is true for all integers.

Another one that works for the integers:
1) Prove the property holds for 0
2) Prove that if the property holds for n, then it holds for n+1
3) Prove that if the property holds for n, then it holds for -n
Then the property is true for all integers

There are endless variations on this theme.
Micrm@ss is offline  
July 25th, 2017, 05:22 AM   #4
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 2,656
Thanks: 681

Quote:
Originally Posted by Antoniomathgini View Post
I've got a question about mathematical induction.

Our first step is to prove that a given theorem holds for "n".
NO. The problem itself is to "prove that a given theorem holds for "n".

The first step is to prove that if the theorem holds for "k" then it holds for k+ 1.

Quote:
Then we prove that rule holds for "n+1"

Finally, we show that a rule holds for 1.
Or for 0 or whatever the base case is. I have a problems that asks you to prove a statement is "true for all n> 6". There the base case is n= 7.

Quote:
If the theorem withstands all of these steps, it means that it not only works for 1 but also all of the numbers above (n+1).
No, all numbers above 1.

Quote:
It would work for 1, 1+1=2, 2+1=3, 4 ... etc.

However, If our theorem deals with 0 or even negative integers, does the process above remain effective when dealing with negatives or do we need to alter the induction process to show that if theorem holds for "n", it must hold for "n-1"?

In other words, does induction ONLY tell us that the rule holds for all integers GREATER than 1?
The way you have phrased it, yes. But the way you have phrased it is not general induction. You can use induction in which the base case is n= 0 and prove the statement true for all non-negative numbers. Or prove the base case n= -1 and show "if the statement is true for k then it is true for k- 1" to prove the statement if true for all negative integers. Or prove the base case n= 0 and prove both ""if the statement is true for k then it is true for k- 1" and "if the statement is true for k then it is true for k+ 1" to prove the statement is true for all integers.
Thanks from Antoniomathgini

Last edited by Country Boy; July 25th, 2017 at 05:25 AM.
Country Boy is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
induction, mathematical



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mathematical induction Lambert1 Abstract Algebra 3 November 7th, 2015 05:33 AM
Mathematical Induction. spuncerj Pre-Calculus 1 November 28th, 2014 04:43 PM
mathematical induction medos Algebra 5 October 31st, 2012 03:54 PM
Help with mathematical induction Sunde Algebra 14 August 3rd, 2011 04:10 PM
Mathematical induction remeday86 Applied Math 1 June 20th, 2010 09:52 AM





Copyright © 2017 My Math Forum. All rights reserved.