My Math Forum Mathematical Induction

 Algebra Pre-Algebra and Basic Algebra Math Forum

 July 14th, 2017, 11:15 AM #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 "n-1"? In other words, does induction ONLY tell us that the rule holds for all integers GREATER than 1?
 July 14th, 2017, 11:32 AM #2 Senior Member   Joined: May 2016 From: USA Posts: 1,047 Thanks: 430 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
July 17th, 2017, 03:31 PM   #3
Senior Member

Joined: Oct 2009

Posts: 428
Thanks: 144

Quote:
 Originally Posted by Antoniomathgini 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.

July 25th, 2017, 05:22 AM   #4
Math Team

Joined: Jan 2015
From: Alabama

Posts: 3,240
Thanks: 884

Quote:
 Originally Posted by Antoniomathgini 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.

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

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top