Demuestra la identidad $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$. Creo que necesito usar el teorema del binomio aquí, pero no sé cómo lidiar con las sumatorias dobles.
¿Conoces una prueba combinatoria de la declaración?
Demuestra la identidad $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$. Creo que necesito usar el teorema del binomio aquí, pero no sé cómo lidiar con las sumatorias dobles.
Vamos a usar la identidad $$ \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}\quad (n\geq k\geq r\geq 0). $$ Intercambiar el orden de la suma y usar la identidad anterior para obtener que $$ \sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} =\sum_{r=0}^{n}\binom{n}{r}\sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{r=0}^n\binom{n}{r}2^{n-r}=(1+2)^n=3^n $$ donde usamos el hecho de que $$ \sum_{k=r}^{n}\binom{n-r}{k-r}=\sum_{u=0}^{n-r}\binom{n-r}{u}=2^{n-r}. $$
Tú sabes que $\displaystyle(1+x)^n=\sum_{k=0}^n\binom nkx^k$
$\displaystyle\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} =\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}=\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{k} \binom{k}{r}1^r$
Dado que $\displaystyle\sum_{r=0}^{k} \binom{k}{r}1^r=(1+1)^k=2^k$, tenemos
$\displaystyle\implies\sum_{k=0}^{n} \binom nk2^k=(1+2)^n=3^n$
Sea $|X|=n$, entonces $3^n$ es el número de funciones de $X$ a {$1,2,3$}.
Cada función de este tipo corresponde de manera única a un par de subconjuntos $(A,B)$ con $A$ un subconjunto de $B$ y $B$ un subconjunto de $X$ tomando $B$ = {$x$ | $f(x)=2$ o $f(x)=3$} y $A$ = {$x$ | $f(x)=2$}.
El número de tales pares de subconjuntos anidados de $X$ es la doble suma en el lado derecho de la fórmula (donde $k$ = $|B|$ y $r$ = $|A|$).
Un aspecto conveniente es que el índice de la suma interna afecta solo a un coeficiente binomial. Al establecer paréntesis podríamos observar
\begin{align*} \color{blue}{\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r}\binom{n}{k}} &=\sum_{k=0}^{n}\left(\sum_{r=0}^{k} \binom{k}{r} \right)\binom{n}{k}\\ &=\sum_{k=0}^{n}2^k \binom{n}{k}\\ &\,\,\color{blue}{=3^n} \end{align*}
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Utilice esta pregunta.
1 votos
Es posible que le interese el teorema multinomial sobre coeficientes multinomiales.