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 :)
$\begingroup$
$\endgroup$
-
$\begingroup$ Any such map can be represented by a two column table with 1,2,3,...,n in the left column and the images of those entries, either 1 or 2, in the right column. How many such tables are there? Use combinatorics. $\endgroup$ – Squid Jan 17 '17 at 15:10
-
2$\begingroup$ You suggested induction. Did you try it? Is there anything wrong with it $\endgroup$ – Taladris Jan 17 '17 at 15:15
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ @Spenser Great answer thanks :), but I don't understand why in the inductive step the range is {0,1}? $\endgroup$ – Alfie Jan 17 '17 at 15:33
-
$\begingroup$
$\endgroup$
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}$.
-
$\begingroup$ This looks very much like a copy of the two other answers... $\endgroup$ – Surb Jan 17 '17 at 15:29
-
1$\begingroup$ Yes, I also just saw it. Possibly because, it took me a while to type it out and in the meantime, the other answers were already posted which I came to know about only after I posted mine. $\endgroup$ – kishlaya Jan 17 '17 at 15:30
$\begingroup$
$\endgroup$
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.
