How to prove the number of all maps of the kind $f : \{1, 2, ..., n\} \to \{1, 2\}$ is $2^n$, for all $n \in\mathbb{N}$? How can I prove 
"The number of all maps of the kind $f : \{1, 2, ..., n\} \to \{1, 2\}$ is $2^n$, for all $n \in\mathbb{N}$?
Using induction?
Thanks :)
 A: Base case. There are two maps $\{1\}\to\{1,2\}$. Either $1\mapsto 1$ or $1\mapsto 2$.
Induction. Suppose that there is $n\geq 1$ such that the number of maps $\{1,\ldots,n\}\to\{1,2\}$ is $2^n$. Then, to specify a map
$$\{1,\ldots,n,n+1\}\to\{1,2\}$$
we first have to specify where $\{1,\ldots,n\}$ goes. There are $2^n$ possibilities by the induction hypothesis. Now, there are only $2$ possibilities for the remaining number $n+1$, so there are $2^n\times 2=2^{n+1}$ possibilities in total.
A: Every element should have a unique image. Therefore, you can give a combinatorial argument as follows:
For each element $e$ in domain, $f(e)$ can be either $1$ or $2$. Hence, for each element in domain there are two possible images and hence a total of $\underbrace{2.2.2...2}_{\text{n times}} = 2^n$ possible maps.
Nevertheless, you can go about using induction also.
For the base case: $f: \{1\} \rightarrow \{1,2\}$, either $f(1) = 1$ or $f(1) = 2$ so $2^1 = 2$ possible maps.
Let the given proposition be true for $n=k$
For $n=k+1$, firstly, restrict your domain to $\{1,2,...,k\}$ so that you know, by induction hypothesis, that there will be $2^k$ possible maps (call this set of maps as $S$). Pick any of the map from $S$. You want to extend this map to $\{1,2,...,k+1\}$ now, which is possible in two ways, namely, $f(k+1) = 0 \text{ or } 1$. Call this new set as $S'$. Since each map in $S$ points to two distinct maps in $S'$ so total number of maps in $S'$ is clearly, $2(2^k) = 2^{k+1}$.
A: To build a map $f\colon \{1,\ldots,n\}\to\{1,2\}$, for every $k\in\{1,\ldots,n\}$ (i.e. $k$ in the domain) you have to choose the value of $f(k)$ in the set $\{1,2\}$ (i.e. a value in the codomain).
So you have $2$ choices for $f(1)$ (either $f(1)=1$ or $f(1)=2$), $2$ choices for $f(2)$, $2$ choices for $f(3)$, and so on...
This gives you:
$$ \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n \text{ times}}= 2^n$$
possible choices which is also the number of such mappings.
