Probar el siguiente por dos métodos diferentes, una combinatoria y uno algebraico

Question

Leer mi libro me encontré con el siguiente problema y estoy buscando ayuda para resolverlo. Me pide que pruebe lo siguiente por dos métodos diferentes, una combinatoria y uno algebraico. Si pudiera conseguir ayuda con uno o ambos ti sería genial, gracias!

Demostrar que esta identidad es verdadera,

$$\binom{n}{k} -\binom{n-3}{k} =\binom{n-1}{k-1} + \binom{n-2}{k-1} + \binom{n-3}{k-1}$$

Answer 1

Combinatoria: Reorganizar a $${n\choose k}={n-1\choose k-1}+{n-2\choose k-1}+{n-3\choose k-1}+{n-3\choose k}$ $

Elegir objetos de $k$ en ${1,2,\ldots, n}$. Esto es contado por LHS. También podemos particionar tales opciones en cuatro partes:

(a) $1$ es el elemento más pequeño de nuestro sistema de $k$.

(b) $2$ es el elemento más pequeño de nuestro sistema de $k$.

(c) $3$ es el elemento más pequeño de nuestro sistema de $k$.

d conjunto de $k$ no contiene ningunos de ${1,2,3}$.

Los cuatro términos de la RHS cuentan sólo estos cuatro casos.

Answer 2

Sugerencia: Poner $\binom{n-3}{k}$ al otro lado y recoger términos.

De esta manera se obtiene a partir de la derecha lateral\begin{align} &\binom{n-1}{k-1}+\binom{n-2}{k-1}+\color{blue}{\binom{n-3}{k-1}+\binom{n-3}{k}}\ &\qquad=\binom{n-1}{k-1}+\color{blue}{\binom{n-2}{k-1}+\binom{n-2}{k}}\ &\qquad=\color{blue}{\binom{n-1}{k-1}+\binom{n-1}{k}}\ &\qquad=\color{blue}{\binom{n}{k}} \end{align}

Answer 3

Utilizar varias veces, la identidad (identidad de Pascal), es decir, $$ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. $$ Tenga en cuenta que \binom $$ \left(\binom{n}{k}-\binom{n-1}{k-1}\right) {n-2} {k-1} - \binom {n-3} {k-1} - \binom {n-3} {k} $ es igual a $$ \binom{n-1}{k}-\binom{n-2}{k-1}-\binom{n-3}{k-1}-\binom{n-3}{k} $ que equivale a $ \binom{n-2}{k}-\binom{n-3}{k-1}-\ Binom {n-3} {k} $ que equivale a \binom{n-3}{k}-\binom{n-3}{k}=0 $$ $$ como se desee.

Answer 4

El siguiente enfoque algebraico es una especie de overkill y por curiosidad solamente. Utilizamos el coeficiente de operador $[x^n]$ para denotar el coeficiente de $x^n$ en una serie. De esta manera podemos escribir por ejemplo\begin{align} \binom{n}{k}=x^k^n \end{align}

Comenzamos con la izquierda y obtener\begin{align} \color{blue}{\binom{n}{k}-\binom{n-3}{k}}&=[x^k]\left((1+x)^n-(1+x)^{n-3}\right)\ &=[x^k]\left((1+x)^3-1\right)(1+x)^{n-3}\ &\color{blue}{=x^k(1+x)^{n-3}}\tag{1} \end{align}

La derecha admite la representación\begin{align} \color{blue}{\binom{n-1}{k-1} }&\color{blue}{+ \binom{n-2}{k-1} + \binom{n-3}{k-1}}\ &=[x^{k-1}]\left((1+x)^{n-1}+(1+x)^{n-2}+(1+x)^{n-3}\right)\ &=[x^{k-1}]\left((1+x)^2+(1+x)+1\right)(1+x)^{n-3}\ &=[x^{k-1}]\left(x^2+3x+3\right)(1+x)^{n-3}\ &\,\,\color{blue}{=[x^k]\left(x^3+3x^2+3x^2\right)(1+x)^{n-3}}\tag{2}\ \end{align}

Desde (1) y (2) coincide la siguiente afirmación.

Answer 5

Para el enfoque combinatorio, considere el siguiente problema: usted tiene el primer $n$ números de $1,\dots,n$ y usted quiere recoger $k$ de ellos de tal manera que escoger al menos uno de $1$, $2$ o $3$. En el lado izquierdo de calcular el número total de opciones menos las opciones en la que usted no escoge cualquiera de $1$,$2$ o $3$. En el lado derecho que suma más de los casos en los que usted escoja $1$ y el otro $k-1$ números, o $2$ y el otro $k-1$ números, pero NO $1$ o $3$ y el otro $k-1$ números, pero NO $1$$2$. Así que tienes dos maneras diferentes de contar la misma cosa.