Prueba de inducción matemática que $\sum\limits_{k=2}^{n-1} {k \choose 2} = {n \choose 3} $

Question

Tengo un problema con una ecuación matemática. No me parece que la solución dada.

Esta es la ecuación: $\sum\limits_{k=2}^{n-1} {k \choose 2} = {n \choose 3} $

Que debo demostrar por inducción que la expresión es correcta para cada $n >= 3$.

Empecé con el principio de la inducción. Para $n = 3$.

$\sum\limits_{k=2}^{2} {2 \choose 2} = 1 = {3 \choose 3} $ Eso es correcto.

Ahora no sé cómo se disuelve la ecuación. La solución debe ser:

$\sum\limits_{k=2}^{n-1} {k \choose 2} + {n \choose 2} = {n \choose 3} + {n \choose 2} = {n + 1 \choose 3} $

Por qué ${n \choose 2}$? Sería estupendo, si alguien me pudiera decir los pasos o dar algunos consejos de cómo podría llegar a esa solución.

Editar: Pues bien, en ese punto estoy:

1. Principio de la inducción: $\sum\limits_{k=2}^{2} {2 \choose 2} = 1 = {3 \choose 3}$

2. Inducción paso n + 1: $\sum\limits_{k=2}^{n} {k \choose 2} + {n \choose 3}$ Eso es mi suposición: ${n \choose 3}$.

3. Cambiar el primer sumando con la asunción, por lo que obtener ${n \choose 2} + {n \choose 3}$

4. Agregar en el coeficiente binomial fórmula: ${n! \choose 2!(n-2)!} + {n! \choose 3!(n-3)!}$

Yo lo tengo como @david-mitra. Qué hay de malo con eso?

Gracias.

Answer 1

Su ecuación es un caso especial de la identidad $$ \sum_{j=k}^{n-m}\binom{j}{k}\binom{n-j}{m}=\binom{n+1}{k+m+1}\tag{1} $$ $m=0$.

% Ecuación $(1)$puede también ser demostrado por inducción, pero también se desprende la identidad $$ \frac{1} {(1-x) ^ {k+1}} = \sum_ {n = k} ^ \infty\binom {n} {k} x ^ {n-k} \tag {2} $$ teniendo $$ \frac{1} {(1-x) ^ {k+1}} \frac {1} {(1-x) ^ {m +1}} = \frac {1} {(1-x) ^ {k + m +2}} \tag {3} $$

Answer 2

HINT $\ $ Probar por inducción$\rm\displaystyle\ f(n)\: = \sum_{\ \: k\ =\ 2_{\phantom .}}^{n-1}\ g(k)\ \iff\ f(n+1) - f(n)\ =\ g(n),\quad f(3) = g(2)$
Luego, su ejercicio se reduce a verificar las ecuaciones RHS (un cálculo polinomio de memoria), a saber.

ps

Para muchos otros ejemplos, vea mis publicaciones anteriores sobre telescopía.

Answer 3

Voy a omitir el inicio de la prueba como dijiste, proporcionaré una prueba combinatoria (por inducción), pero para$n\ge 3$ para elegir$3$ elemento de$n+1$ item fix último elemento$a_{n+1}$ entonces tiene:

1. Usted selecciona el último artículo con dos elementos de los primeros n artículos, que es${n \choose 2}$
2. Usted selecciona los tres elementos del primer$n$ elementos y, como paso previo a la inducción, es$\sum\limits_{k=2}^{n-1} {k \choose 2}$

Entonces tu forma total posible (para$n+1$) es:

ps

Answer 4

Queremos demostrar: $$ \sum_{k=2}^{n-1} {k\elegir 2}= {n\choose3},\quad n\ge3.\la etiqueta{1} $$

Si quieres demostrar que la ecuación (1) tiene para todos los $n\ge 3$ el uso de la inducción:

1) Demostrar que la ecuación es verdadera para $n=3$:

$$ \sum_{k=2}^{3-1} {k\elegir 2}= {2\choose2}= {3\choose3}.\la etiqueta{1} $$

2) Suponga que la ecuación es verdadera para $n=m$: $$ \color{color granate}{\sum_{k=2}^{m-1} {k\elegir 2}}= \color{color granate}{m\choose3 }. $$

3) demostrar que la ecuación debe ser verdadera para $n=m+1$:

$$\eqalign{ \sum_{k=2}^{(m+1)-1} {k\elegir 2} &=\sum_{k=2}^{m } {k\elegir 2}\cr &=\sum_{k=2}^{m-1 } {k\choose2} +\color{verde oscuro de}{\sum_{k=m}^m {k\choose2}}\cr &=\biggl[\ \color{color granate}{ \sum_{k=2}^{m-1 } {k\elegir 2}}\ \biggr]+\color{verde oscuro}{m\choose2}\cr &= \color{color granate}{ m\elegir 3} +{m\choose2}\cr y= {m!\(m-3)! 3!}+ {m!\(m-2)! 2!}\cr y={ m(m-1)(m-2)\más de 3!} +{ m(m-1) \a más de 2!} \cr &= m(m-1)({m-2\más de 6}+{3\más de 6 })\cr y= { m(m-1)(m+1)\más de 6} \cr y={m+1\elegir 3}. } $$