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$ 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

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$ @Alfie That was a typo. $\endgroup$ – Spenser Jan 17 '17 at 15:37

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.