How to prove by induction that there are $2^n$ binary $n$-vectors. 
prove by induction that there are $2^n$ binary $n$-vectors.

So, I take $1$ as the base case:
$$A(1) = 2^1=2 : \begin{bmatrix}0\end{bmatrix}_1,\begin{bmatrix}1\end{bmatrix}_2$$
$$A(2) = 2^2=4 : \begin{bmatrix}0\\1\end{bmatrix}_1,\begin{bmatrix}1\\0\end{bmatrix}_2, \begin{bmatrix}1\\1\end{bmatrix}_3,\begin{bmatrix}0\\0\end{bmatrix}_4$$
.
.
.I assume it's true for $k$
$$A(k) = 2^k : \begin{bmatrix}0\\1\\ \vdots \\a_i\\ \vdots \\a_k\end{bmatrix}_1,\begin{bmatrix} 1 \\ 0 \\ \vdots \\ a'_i \\ \vdots \\ a'_k \end{bmatrix}_2, \ldots,\begin{bmatrix}1\\0\\ \vdots \\ a''_i \\ \vdots \\a''_k\end{bmatrix}_{2^k} \mid ∀a_i''^{\cdots}[a_i''^{\cdots} = 0 \oplus a_i''^{\cdots} = 1] \mid k\ge 1$$
$$A(k+1) = 2^{k+1} : \begin{bmatrix} 0 \\ 1 \\ \vdots \\a_i\\ \vdots \\ a_k \end{bmatrix}_1, \begin{bmatrix}1\\0\\ \vdots \\a'_i\\ \vdots\\ a'_k\end{bmatrix}_2, \ldots, \begin{bmatrix} 1 \\ 0 \\ \vdots \\a''_i\\ \vdots \\ a''_k \end{bmatrix}_{2^k}, \begin{bmatrix} 1 \\ 0 \\ \vdots \\ a'''_i\\ \vdots \\ a'''_k \end{bmatrix}_{2^{k+1}}$$
But I get stuck here, I don't know how to prove that $A(k)+1=A(k+1)$, do you have any ideas? 
Thanks in advance
 A: For each $n-1$-vector you can append either a $0$ or a $1$ as its $n$th-coordinate to create an $n$-vector. So $A(k)=2A(k-1)$. If $A(k-1)=2^{k-1}$, then the result follows.
A: You can see a $n$ dimensional vector with binary inputs as the characteristic function the subsets of a set of size $n$, for example, $\{0,1,...,n-1\}$.
This is, you know that $\{0,1,3\}\subseteq\{0,1,...,n-1\}$ if  $n\geq 5$, so, the vector $(1,1,0,1,0,...,0)$ represents the characteristic function of $\{0,1,3\}$. This means that the input $x_i=1$, $(1\leq i\leq n)$ iff $i\in\{0,1,3\}$ and $x_i=0$ in other case.
Now, you can count the number of subset of size $k\leq n$ in $\{0,1,...,n-1\}$ with the binomial coefficient $\binom{n}{k}$ and, in this context you want count the number of subsets of $\{0,1,...,n-1\}$. So, you need calculate $\sum_{k=0}^n\binom{n}{k}$. But this is easy because by the binomial theorem you have
$$2^n=(1+1)^n=\sum_{k=0}^n\binom{n}{k}1^k1^{n-k}=\sum_{k=0}^n\binom{n}{k}$$
A: A binary $n+1$ vector $(x_1,x_2,\dotsc, x_n, y)$ can be written as $(x,y)$ where $x$ is a binary n-vector. There are $2^n$ choices for $x$ by the inductive hypothesis and $2$ choices for $y$. Hence there are 
$$
2^n\times 2
$$
binary $n+1$ vectors.
A: Here's your list of $k$-vectors:
$$
\underbrace{ \begin{bmatrix} \vdots \\ \vdots \\ \vdots \end{bmatrix}, \ldots\ldots\ldots, \begin{bmatrix} \vdots \\ \vdots \\ \vdots \end{bmatrix} }_{\large \text{This list has $2^k$ items.}}
$$
Here's your list of $(k+1)$-vectors:
$$
\underbrace{ \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 0 \end{bmatrix}, \ldots\ldots\ldots, \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 0 \end{bmatrix} }_{\large \text{This list has $2^k$ items.}},\, \underbrace{ \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 1 \end{bmatrix}, \ldots\ldots\ldots, \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 1 \end{bmatrix} }_{\large \text{This list has $2^k$ items.}}
$$
You have two copies of the same list, except that $0$ has been appended at the bottom of every item in the first copy and $1$ has been appended at the bottom of every item in the second.
Thus the number of items is $2^k\times 2 = 2^{k+1}.$
