¿Cómo demostrar esta identidad de forma combinatoria?

Question

\begin{equation} \sum_{k=0}^{n}\left( $$\begin{array}{c}{2 n+1} \\ {k}\end{array}$$ \N - derecha)=2^{2 n} \end{ecuación} He conseguido demostrarlo de forma algebraica pero no combinatoria.

Gracias.

No es un duplicado.

Answer 1

Dejemos que $S=\{1,2,\dots,2n+1\}$ .

Queremos demostrar que $\mathcal{A}=\{A\subseteq S:~|A|\leq n\}$ está en biyección con $\mathcal{B}=\{B\subseteq S:~2n+1\notin B\}$ . Está claro que $|\mathcal{A}|$ se cuenta por el LHS de su identidad mientras que $|\mathcal{B}|$ se cuenta por el RHS de su identidad.

Considere la función $f:\mathcal{A}\to\mathcal{B}$ dado por:

$$f(A) = \begin{cases} A&\text{if }2n+1\notin A\\ S\setminus A&\text{if }2n+1\in A\end{cases}$$

Tenga en cuenta que si $2n+1\notin A$ entonces $|f(A)|=|A|\leq n$ . Por otro lado, si $2n+1\in A$ entonces $|f(A)|=|S\setminus A| = 2n+1-|A|\geq n+1$

Supongamos entonces que $f(A_1) = f(A_2)$ . Esto implica que, o bien $2n+1$ está en ambos $A_1$ y $A_2$ o no está en ninguna de las dos. En el primer caso, eso implicaría que $A_1=A_2$ . De lo contrario, eso implicaría que $S\setminus A_1=S\setminus A_2$ lo que a su vez implica que $A_1=A_2$ . Por lo tanto, la función es inyectiva.

Para la subjetividad, considere un subconjunto arbitrario $B$ que no contenga $2n+1$ de $S$ . En el caso de que $|B|\leq n$ entonces $B\in\mathcal{A}$ y $f(B)=B$ . En caso contrario, si $|B|\geq n+1$ tenemos $S\setminus B\in \mathcal{A}$ y que $f(S\setminus B)=B$ .

Por lo tanto, la función es una biyección y se demuestra la identidad.