Prueba combinatoria de$3^n - 2^n = \sum_{i=0}^{n-1}2^i3^{n-1-i}$

Question

$3^n - 2^n = \sum_{i=0}^{n-1}2^i3^{n-1-i}$

En primer lugar, estoy tratando de averiguar lo que ambos lados cuentan.
El lado izquierdo cuenta el número de $\{0,1,2\}$ cadenas menos el número de $\{0,1\}$ cadenas. Sin embargo, siento que esta no es una forma intuitiva de verlo y probablemente hay una mejor manera de contar el lado izquierdo que puede hacer que la igualdad sea más fácil de entender.

Answer 1

El LHS cuenta el número de cadenas de longitud- $n$ en $\{0,1,2\}$ que contiene al menos un $2$ .

Entonces, considere la primera posición donde aparece un $2$ . Antes de ese punto, debe ser una cadena de $\{0,1\}$ , y después de ese punto puede ser cualquier cadena de $\{0,1,2\}$ , dando el RHS.

Answer 2

Como nota, el lado izquierdo cuenta el número de $n$-dígito de las cadenas sobre el alfabeto $\{0,1,2\}$ menos el número de $n$-dígito de las cadenas sobre el alfabeto $\{0,1\}$. Por lo tanto, el lado izquierdo cuenta el número de $n$dígitos cadenas de más de $\{0,1,2\}$ que contienen al menos un $2$.

Denotamos como $S$ el conjunto de $n$dígitos cadenas de más de $\{0,1,2\}$ que contienen al menos un $2$, cuya cardinalidad queremos contar. Partición de $S$ en los conjuntos de $S_0$ través $S_{n-1}$, donde $S_i$ es el número de $n$dígitos cadenas de más de $\{0,1,2\}$ que contienen al menos un $2$, y en el primer $2$ es en el $i+1$-st posición. Es fácil ver que $S=\bigcup_{i=0}^{n-1}S_i$. (La primera $2$ debe ser en una de las posiciones $1$ través $n$, y los conjuntos de $S_i$ partición $S$, como ninguna cadena puede tener su primera $2$ en más de una posición.

Las cadenas en $S_i$ debe comenzar con $i$ dígitos de $\{0,1\}$ ($2^i$ posibilidades), debe tener el dígito $2$ en la $i+1$st posición ($1$ posibilidad), y debe terminar con $n-i-1$ dígitos de $\{0,1,2\}$ ($3^{n-i-1}$ posibilidades). A través de la multiplicación y la adición de los principios de conteo, la cardinalidad de $S_i$ es $\sum_{i=0}^{n-1}2^i3^{n-1-i}$.

Answer 3

Supongamos que estamos contando el número de $\{0,1,2\}$ cadenas de longitud $n$ que ha $2$ en ella.

LHS: $\text{[Number of all such strings]} - \text{[Number of strings consist of only $0,1$]}$ .

HR: en primer lugar poner a $2$ para el primer dígito y luego para el resto de la $n-1$ dígitos, se puede poner cualquier cosa con $3^{n-1}$. A continuación, coloque $2$ para el segundo dígito. Ahora, nos contó el caso donde hay un $2$ en el primer dígito a fin de poner $0$ o $1$ al primer dígito con $2$ opciones y podemos poner cualquier cosa a $n-2$ dígitos después de la $2$ con $3^{n-2}$. Por lo tanto, tenemos $2\cdot3^{n-2}$ opciones. De continuar así, en la final poner $2$ para el último dígito y podemos poner $0$ o $1$ a primera $n-1$ dígitos con $2^{n-1}$. A continuación, en total, tenemos $\sum_{n=0}^{n-1}2^i3^{n-1-i}$ cadenas que tienen $2$ en ella.