Cómo probar por inducción que hay $2^n$ binarias $n$-vectores.

Question

demostrar por inducción que hay $2^n$ binarias $n$-vectores.

Así que, aprovecho $1$ como el caso base:

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

. . .Supongo que es cierto para $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}}$$

Pero me quedo atascado aquí, no sé cómo demostrar que $A(k)+1=A(k+1)$, ¿tienes alguna idea?

Gracias de antemano

Answer 1

Para cada una de las $n-1$-vector puede anexar un $0$ o $1$ como $n$th-coordinar a crear un $n$-vector. Por lo $A(k)=2A(k-1)$. Si $A(k-1)=2^{k-1}$, entonces el resultado de la siguiente manera.

Answer 2

Usted puede ver una $n$ dimensiones de vectores con entradas binarias como la función característica de los subconjuntos de un conjunto de tamaño $n$, por ejemplo, $\{0,1,...,n-1\}$.

Esto es, usted sabe que $\{0,1,3\}\subseteq\{0,1,...,n-1\}$ si $n\geq 5$, por lo tanto, el vector $(1,1,0,1,0,...,0)$ representa la función característica de $\{0,1,3\}$. Esto significa que la entrada $x_i=1$, $(1\leq i\leq n)$ iff $i\in\{0,1,3\}$ e $x_i=0$ en otro caso.

Ahora, usted puede contar el número de subconjuntos de tamaño $k\leq n$ en $\{0,1,...,n-1\}$ con el coeficiente binomial $\binom{n}{k}$ y, en este contexto desea contar el número de subconjuntos de $\{0,1,...,n-1\}$. Así, es necesario calcular el $\sum_{k=0}^n\binom{n}{k}$. Pero esto es fácil ya que por el teorema del binomio se han $$2^n=(1+1)^n=\sum_{k=0}^n\binom{n}{k}1^k1^{n-k}=\sum_{k=0}^n\binom{n}{k}$$

Answer 3

Un binario $n+1$ vector de $(x_1,x_2,\dotsc, x_n, y)$ puede ser escrito como $(x,y)$ donde $x$ es un binario de n-vector. Hay $2^n$ opciones para $x$ por la hipótesis inductiva y $2$ opciones para $y$. Por lo tanto, hay $$ 2^n\times 2 $$ binario $n+1$ vectores.

Answer 4

Aquí está su lista de $k$-vectores: $$ \underbrace{ \begin{bmatrix} \vdots \\ \vdots \\ \vdots \end{bmatrix}, \ldots\ldots\ldots, \begin{bmatrix} \vdots \\ \vdots \\ \vdots \end{bmatrix} }_{\large \text{Esta lista ha $2^k$ elementos.}} $$ Aquí está su lista de $(k+1)$-vectores: $$ \underbrace{ \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 0 \end{bmatrix}, \ldots\ldots\ldots, \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 0 \end{bmatrix} }_{\large \text{Esta lista ha $2^k$ elementos.}},\, \underbrace{ \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 1 \end{bmatrix}, \ldots\ldots\ldots, \begin{bmatrix} \vdots \\ \vdots \\ \vdots \\ 1 \end{bmatrix} }_{\large \text{Esta lista ha $2^k$ elementos.}} $$ Tiene dos copias de la misma lista, salvo que el $0$ ha sido añadida en la parte inferior de cada elemento de la primera copia y $1$ ha sido añadida en la parte inferior de cada elemento en el segundo.

Por lo tanto el número de elementos es $2^k\times 2 = 2^{k+1}.$