Combinatoria prueba de $\sum\limits_{k=0}^n {n \choose k}3^k=4^n$

Question

Mediante la siguiente ecuación:

$$\sum_{k=0}^n {n \choose k}3^k=4^n$$

Necesito demostrar que ambos lados de la ecuación a resolver el mismo problema combinatorio.

Es fácil ver que el lado derecho de la ecuación es contar el número de maneras de dividir a $n$ diferentes bolas en $4$ cubos.

¿Es correcto decir que el lado izquierdo de la ecuación a resolver el mismo problema de la siguiente manera (?):

Desde $\sum\limits_{k=0}^n {n \choose k} 3^k= \sum\limits_{k=0}^n {n \choose n-k}3^k$, podemos cambiar la ecuación:

$$\sum_{k=0}^n {n \choose n-k}3^k=4^n$$

Y de la nueva ecuación, es fácil ver que cada coeficiente binomial elige el número de bolas a poner en el primer cubo, y $3^k$ divide el resto $k$ bolas entre el resto de 3 cubos sin limitación.

Answer 1

Sí, estoy de acuerdo con tu interpretación de la izquierda lado, y también lhf's comentario puede ser visto de la misma manera:

1. $4^n$ de las maneras de dividir $n$ bolas en $4$ cajas
2. $(3+1)^n$ el mismo que el anterior
3. $ \sum_{k=0}^n {n \choose k} 1^{n-k} 3^k$ por cada $k$, el de las formas para elegir a $k$ bolas entre el $n$ pelotas que tienen, a veces la manera de poner la $n-k$ pelotas en una caja, los tiempos de las maneras de poner el resto de $k$ bolas en el resto de $3$ cajas
4. $\sum_{k=0}^n {n \choose k}3^k$ como en el anterior, el uso de $1^{n-k}=1$