
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
July 14th, 2017, 12:15 PM  #1 
Member Joined: Apr 2017 From: Canada Posts: 32 Thanks: 2  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 "n1"? In other words, does induction ONLY tell us that the rule holds for all integers GREATER than 1? 
July 14th, 2017, 12:32 PM  #2 
Senior Member Joined: May 2016 From: USA Posts: 883 Thanks: 353 
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 nonnegative integers. Now prove that P(n) and n > 0 proves P(n). 
July 17th, 2017, 04:31 PM  #3  
Senior Member Joined: Oct 2009 Posts: 190 Thanks: 74  Quote:
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 n1 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.  
July 25th, 2017, 06:22 AM  #4  
Math Team Joined: Jan 2015 From: Alabama Posts: 2,922 Thanks: 785  Quote:
The first step is to prove that if the theorem holds for "k" then it holds for k+ 1. Quote:
Quote:
Quote:
Last edited by Country Boy; July 25th, 2017 at 06:25 AM.  

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 06:33 AM 
Mathematical Induction.  spuncerj  PreCalculus  1  November 28th, 2014 05:43 PM 
mathematical induction  medos  Algebra  5  October 31st, 2012 04:54 PM 
Help with mathematical induction  Sunde  Algebra  14  August 3rd, 2011 05:10 PM 
Mathematical induction  remeday86  Applied Math  1  June 20th, 2010 10:52 AM 