La obtención de los coeficientes binomiales, "sin contar los subconjuntos" argumento

Question

Quiero obtener la fórmula para los coeficientes binomiales de la siguiente manera: primaria anillo teoría muestra que la $(X+1)^n\in\mathbb Z[X]$ es un grado $n$ polinomio, para todos los $n\geq0$, así que podemos escribir

$$(X+1)^n=\sum_{k=0}^na_{n,k}X^k\,,\ \style{font-family:inherit;}{\text{with}}\ \ a_{n,k}\in\mathbb Z\,.$$

Utilizando el hecho de que $(X+1)^n=(X+1)^{n-1}(X+1)$ $n\geq1$ y la definición de producto de polinomios, obtenemos la siguiente relación de recurrencia para todos los $n\geq1$:

$$a_{n,0}=a_{n,n}=1;\ a_{n,k}=a_{n-1,k}+a_{n-1,k-1}\,,\ \style{font-family:inherit;}{\text{for}}\ k=1,\dots,n-1\,.$$

Quiero saber si hay una manera de manipular esta recurrencia con el fin de obtener directamente los valores de los coeficientes $a_{n,k}$, es decir,$a_{n,k}=\binom nk=\frac{n!}{k!(n-k)!}$.

Tenga en cuenta que el enfoque habitual a través de la generación de funciones, definitivamente, no va a funcionar, al menos en el espíritu de mi pregunta, ya que este método sólo funciona cuando sabemos de antemano los coeficientes de la generación de la función (ya sea por el "número de $k$-subconjuntos" argumento, o la serie de Maclaurin para $(X+1)^n$, o de otra cosa), y esto es precisamente lo que quiero evitar.

Esta pregunta está estrechamente relacionado con la reciente cuestión de la mina. De hecho la misma pregunta, con los números de Bernoulli, en lugar de los coeficientes binomiales.

EDITAR

Yo no considerar como válida la manipulación de la siguiente "mágico" argumento: "la secuencia de $(b_{n,k})$ $b_{n,k}=\frac{n!}{k!(n-k)!}$ obedece a la misma periodicidad y las condiciones iniciales como $(a_{n,k})$, lo $a_{n,k}=b_{n,k}$ todos los $n,k$. ¿Cómo obtener la fórmula para la $b_{n,k}$ en el primer lugar? Bueno, usted puede ir a través de la "contar los subconjuntos" argumento, pero esto es precisamente lo que no quiero hacer. Lo mismo se aplica a mi pregunta o duda acerca de los números de Bernoulli.

Answer 1

Un simple enfoque es resolver las dos variables de la recurrencia de la relación de forma iterativa, es decir, el saber $a_{n,0}$$a_{n,1}$,$a_{n,2}$, etc.

Debemos tener
$$\begin{eqnarray*} a_{n,1} &=& a_{n-1,1}+a_{n-1,0} \\ &=& a_{n-1,1}+1, \qquad a_{1,1}=1. \end{eqnarray*}$$ Esta es una variable de la recurrencia de la relación de la forma $$b_n = b_{n-1}+1, \qquad b_1 = 1.$$ Esto se puede resolver por los métodos habituales. Nos encontramos $a_{n,1} = n.$

A continuación tenemos $$\begin{eqnarray*} a_{n,2} &=& a_{n-1,2}+a_{n-1,1} \\ &=& a_{n-1,2}+n-1, \qquad a_{2,2}=1. \end{eqnarray*}$$ Este es otro sencillo de la recurrencia de la relación. Nos encontramos $a_{n,2} = n(n-1)/2.$

En el siguiente paso, $$\begin{eqnarray*} a_{n,3} &=& a_{n-1,3}+a_{n-1,2} \\ &=& a_{n-1,3} + \frac{1}{2}(n-1)(n-2), \qquad a_{3,3}=1. \end{eqnarray*}$$ Esto implica $a_{n,3} = n(n-1)(n-2)/6.$

Este proceso se puede repetir para edificar $a_{n,k}$ cualquier $k$. En algún punto de un patrón se va a notar y el principio de la inducción puede ser aplicado.

Answer 2

Si definimos $a_{n,k}=\binom nk$ a ser el coeficiente de $X^k$ $(1+X)^n$ (sin combinatoria significado), entonces usted puede fácilmente encontrar $\binom nk=\binom {n-1}{k-1}+\binom{n-1}k$ todos los $n,k\geq1$ (como se indicó en la pregunta). También se $\binom n0=1$ todos los $n\geq0$, e $\binom0k=0$ todos los $k>0$. Ampliando el segundo término de la relación de recurrencia de forma recursiva, con $\binom0k=0$ como la terminación de la cláusula, da $$ \binom n k=\sum_{0\leq i<n}\binom i{k-1} \qquad\text{para $k\geq1$ y todos los $n\geq0$.} $$ Ahora, desde el hecho de que $n\mapsto\binom n0$ es una función polinómica (de $n\in\mathbf N$) de grado$~0$ (es decir, la función constante$~1$) se deduce fácilmente por inducción que $n\mapsto\binom nk$ es una función polinómica de grado$~k$ (suma de una función polinómica de$~n$ aumenta el grado por$~1$). Por otra parte la primera $k$ valores $\binom ik$ $0\leq i<k$ del polinomio de la función son todos los$~0$, por lo que el polinomio tiene raíces $0,1,2,\ldots,k-1$. Por lo tanto, necesariamente toma la forma $\binom nk=c_k(n-0)(n-1)\ldots(n-(k-1))$ para algunas constantes $c_k$. El uso de la recursividad (en algún momento uno tiene que calcular algo) el primer término distinto de cero $\binom kk$ de la secuencia de $n\mapsto\binom nk$ puede ser demostrado ser$~1$ por cada$~k$, y de ello se sigue que $c_k=1/(k(k-1)(k-2)\ldots(k-(k-1))=\frac1{k!}$. Entonces $$ \binom nk = \frac{n(n-1)\ldots(n-(k-1))}{k!}, $$ que usted puede, si usted se siente inclinado a escribir como $\binom nk = \frac{n!}{k!(n-k)!}$ mientras $k\leq n$.

Mira mamá, sin contar!

Answer 3

Creo que Mathematica comando para la solución de la recurrencia de la relación puede ser utilizado:

RSolve[{a[n,k]==a[n-1,k]+a[n-1,k-1],a[n,0]==1,un[n,n]==1},un[n,k],{n,k}]