prueba inductiva $\binom{2n}{n}$

Question

Quiero demostrar la siguiente identidad mediante la inducción (no doble método de recuento). Aunque es una versión específica de Vandermonde de la identidad y de su inductivo prueba se presenta aquí, pero necesito un directo inductivo de la prueba en este, no la forma general.

$$\binom{2n}{n}=\sum\limits_{k=0}^n\binom{n}{k}^2$$

He tratado de simplificar $\binom{2n+2}{n+1}$ mediante el uso del teorema de Pascal, pero no se obtiene ningún resultado. Alguna ayuda?

Answer 1

Supongamos que $$ \sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}\etiqueta{1} $$ entonces $$ \begin{align} \sum_{k=0}^{n+1}\binom{n+1}{k}^2 &=\sum_{k=0}^{n+1}\left[\binom{n}{k}+\binom{n}{k-1}\right]^2\tag{2a}\\ &=\sum_{k=0}^{n+1}\left[\binom{n}{k}^2+\binom{n}{k-1}^2+2\binom{n}{k}\binom{n}{k-1}\right]\tag{2b}\\ &=\binom{2n}{n}\left(1+1+\frac{2n}{n+1}\right)\tag{2c}\\ &=\binom{2n+2}{n+1}\tag{2d} \end{align} $$ Explicación:
$\text{(2a)}$: Triángulo de Pascal identidad
$\text{(2b)}$: álgebra
$\text{(2c)}$: aplicar $(1)$ $(3)$
$\text{(2d)}$: $\binom{2n+2}{n+1}=\frac{4n+2}{n+1}\binom{2n}{n}$

---

Lema: $$ \sum_{k=1}^n\binom{n}{k}\binom{n}{k-1}=\frac{n}{n+1}\sum_{k=0}^n\binom{n}{k}^2\etiqueta{3} $$ Prueba:

Desde $\binom{n}{k-1}=\frac{k}{n-k+1}\binom{n}{k}$,$\binom{n}{k}+\binom{n}{k-1}=\frac{n+1}{n-k+1}\binom{n}{k}$. Por lo tanto, $$ \frac{n-k+1}{n+1}\left[\binom{n}{k}+\binom{n}{k-1}\right]\binom{n}{k-1}=\binom{n}{k}\binom{n}{k-1}\tag{3a} $$ Desde $\binom{n}{k}=\frac{n-k+1}{k}\binom{n}{k-1}$,$\binom{n}{k}+\binom{n}{k-1}=\frac{n+1}{k}\binom{n}{k-1}$. Por lo tanto, $$ \frac{k}{n+1}\left[\binom{n}{k-1}+\binom{n}{k}\right]\binom{n}{k}=\binom{n}{k-1}\binom{n}{k}\etiqueta{3b} $$ La adición de $(3a)$ $(3b)$ y la cancelación de los rendimientos $$ \frac{n-k+1}{n+1}\binom{n}{k-1}^2+\frac{k}{n+1}\binom{n}{k}^2=\binom{n}{k-1}\binom{n}{k}\etiqueta{3c} $$ Sumando $(3c)$$k$, y la sustitución de $k\mapsto k+1$ en la suma de la izquierda, da $$ \frac{n}{n+1}\sum_{k=0}^n\binom{n}{k}^2=\sum_{k=1}^n\binom{n}{k-1}\binom{n}{k}\etiqueta{3d} $$ QED

Answer 2

En general, se puede demostrar por inducción que $$\frac{d^n}{dt^n} f(t)g(t) = \sum_{k=0}^n \binom{n}{k} \biggl(\frac{d^k}{dt^k}f(t) \biggr) \biggl(\frac{d^{n-k}}{dt^{n-k}}g(t) \biggr). \tag{1} $ $ para $0 \le k \le r$ enteros, se puede ver por la inducción que $$\frac{d^k}{dt^k} t^r = r(r-1)\cdots(r-k+1)t^{r-k} = k!\binom{r}{k}t^{r-k}. $ $ tan en particular, $$\frac{d^n}{dt^n} t^{2n} = n!\binom{2n}{n}t^n. \tag{2} $$ aplicando $(1)$ $f(t) = g(t) = t^n$ da\begin{align} \frac{d^n}{dt^n} t^{2n} &= \sum_{k=0}^n \binom{n}{k} \biggl(\frac{d^k}{dt^k}t^{n} \biggr) \biggl(\frac{d^{n-k}}{dt^{n-k}}t^{n} \biggr) \\ &= \sum_{k=0}^n \binom{n}{k} \cdot k!\binom{n}{k}t^{n-k} \cdot (n-k)!\binom{n}{n-k} t^k \\ &= \sum_{k=0}^n n! \binom{n}{k}^2 t^n. \tag{3} \end {Alinee el} comparando $(2)$ y $(3)$ dan el resultado deseado.