1. ## 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?

2. ## 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$.