Results 1 to 2 of 2

Thread: Proof by induction

  1. #1
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    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 10:56 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,631
    Thanks
    1457

    Re: Proof by induction

    Suppose $\displaystyle A = \{a_1, \ldots, a_{n-1}, a_n\}$. A single map from $\displaystyle 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 $\displaystyle m^{n-1}$ possible functions that map $\displaystyle A \setminus \{a_n\}$ to $\displaystyle B$. For any of those maps, we need to choose what $\displaystyle a_n$ maps to in order to extend the function to a function from $\displaystyle A \to B$. We have $\displaystyle m$ elements of B to choose from, completely independent from the choices for the mappings of $\displaystyle a_1, \ldots, a_{n-1}$. Thus, for each such map, we have $\displaystyle m$ different functions that extend the map to a map to all of $\displaystyle A$. Then, there are $\displaystyle m^{n-1}\cdot m = m^n$ total functions from $\displaystyle A \to B$.
    Last edited by SlipEternal; Nov 28th 2017 at 11:27 AM.
    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, 08:12 AM
  2. Induction Proof Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 15th 2010, 10:16 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM
  5. induction proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jan 21st 2008, 12:48 AM

/mathhelpforum @mathhelpforum