Demostración de la identidad combinatoria mediante el principio de inclusión-exclusión

Question

Necesito probar la identidad ${\displaystyle \sum_{k=0}^{n}(-1)^{k}{2n-k \choose k}2^{2n-2k}=2n+1} $ utilizando el principio de inclusión-exclusión. Se sugirió pensar en el número de maneras de colorear los números ${1,..,2n}$ en los colores rojo y azul tal que si $i$ es de color rojo por lo que es $i-1$ . Bueno, está claro que el número de formas de hacerlo es $2n+1$ pero no consigo demostrar por qué también es igual al lado izquierdo de la ecuación.

¿Alguien puede darme una pista sobre los conjuntos que debo definir para utilizar el principio de inclusión-exclusión? Gracias.

Answer 1

Existen $2^{2n}$ colorantes en total, $2^{2n-2}{2n-1\choose 1}$ formas de elegir un par de números adyacentes y colorear el primero de azul y el segundo de rojo y el resto de cualquier color, $2^{2n-4}{2n-2\choose 2}$ formas de elegir dos pares de números y tener ambos con el primer color azul y el segundo color rojo y el resto de cualquier color, y así sucesivamente.