Results 1 to 2 of 2

Thread: Proof by induction

  1. #1
    Newbie
    Joined
    Nov 2017
    From
    South Asia
    Posts
    7

    Question 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 inayat; Nov 28th 2017 at 11:56 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: Proof by induction

    Suppose A = \{a_1, \ldots, a_{n-1}, a_n\}. A single map from A \setminus \{a_n\} \mapsto B is a map from a set with n-1 elements to a set with m elements. By the induction hypothesis, there are m^{n-1} possible functions that map A \setminus \{a_n\} to B. For any of those maps, we need to choose what a_n maps to in order to extend the function to a function from A \to B. We have m elements of B to choose from, completely independent from the choices for the mappings of a_1, \ldots, a_{n-1}. Thus, for each such map, we have m different functions that extend the map to a map to all of A. Then, there are m^{n-1}\cdot m = m^n total functions from A \to B.
    Last edited by SlipEternal; Nov 28th 2017 at 12:27 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 14th 2017, 09:12 AM
  2. Induction Proof Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 15th 2010, 11:16 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 10:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 02:20 PM
  5. induction proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jan 21st 2008, 01:48 AM

/mathhelpforum @mathhelpforum