Prueba combinatoria para $n\ge1$ de $3^n = \sum_{k=0}^n \binom{n}{k}(2^{n-k})$

Question

Sé que se supone que tenemos que buscar cadenas con n entradas que estén en {0,1,2} (una cadena ternaria), pero no sé muy bien a dónde ir.

Answer 1

Para el lado izquierdo, el principio de multiplicación da como resultado $|\{0,1,2\}|^n=3^n$ cuerdas. Para el lado derecho, condicionar el número $k$ de $0$ s. Hay $\binom{n}{k}$ opciones de $k$ entradas para el $0$ s y $|\{1,2\}|^{n-k}=2^{n-k}$ opciones para el resto de $n-k$ entradas no nulas.

Answer 2

Una pista: Intenta contar el número de formas de ordenar $n$ personas en $3$ grupos, donde cada persona debe estar exactamente en un grupo, de dos maneras.

Subhint para el lado derecho:

Intente utilizar el trabajo de casos basado en el número de personas en uno de los grupos.

Observación: Esto es lo mismo que el argumento que tienes en mente con las cadenas. Cada una de las $n$ puntos de la cadena representa una persona, y cada uno de $0,1,$ et $2$ representan el grupo en el que estaría esa persona.

Answer 3

$(1+2)^n=\Sigma_{k=0}^{k=n}\binom{n}{k}2^{n-k}$ utilizando la expansión del teorema del Binomio de $(1+x)^{n}$ utilizando $x=2$ .