My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Reply
 
LinkBack Thread Tools Display Modes
November 28th, 2017, 11:51 AM   #1
Newbie
 
Joined: Oct 2017
From: Rumba

Posts: 9
Thanks: 0

Proof by induction


Would i be ok to use base step as n = 1 for a function A -> B for one in A

A (x) mapping to B (a1,a2,a3.... am)

No of functions possible for n-1 is m^n

I dont know how to go on with the induction step any ideas?

Last edited by sita; November 28th, 2017 at 11:57 AM.
sita is offline  
 
November 28th, 2017, 12:05 PM   #2
Senior Member
 
Joined: May 2016
From: USA

Posts: 857
Thanks: 348

To prove by weak mathematical induction the proposition

$P(n) \text { is true for any } n \in \mathbb N^+$,

first prove $P(1) \text { is true.}$ This is frequently very easy to do.

Moreover it justifies the following statement:

$\exists \text { at least one number } k \in \mathbb N^+ \text { such that } P(k) \text { is true.}$

This is frequently called the assumption step although it is clearly a true statement. Notice however, that you may NOT assume that k = 1. You may assume that $k \ge 1.$

Now prove in the second step that

$P(k + 1) \text { is true.}$

What is the intuition?

P(1) is true by the first step so P(1 + 1) = P(2) is true by the second step, so P(2 + 1) = P(3) is true by the second step, so P(3 + 1) = P(4) is true by the second step, and so on forever.

Last edited by JeffM1; November 28th, 2017 at 12:08 PM.
JeffM1 is offline  
Reply

  My Math Forum > Math Forums > Math

Tags
induction, proof



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proof by induction Jimi Algebra 2 March 10th, 2014 07:41 AM
proof by induction walter r Calculus 3 April 26th, 2013 05:25 AM
Proof by induction 3,14oner Abstract Algebra 4 April 11th, 2012 01:37 AM
proof by induction Airmax Applied Math 9 May 8th, 2009 01:02 PM
proof by induction MaD_GirL Number Theory 5 November 14th, 2007 07:34 PM





Copyright © 2017 My Math Forum. All rights reserved.