Resolver una recurrencia (con la forma de una convolución) que involucra coeficientes binomiales

Question

Tratando un problema relacionado con la intersección de hiperplanos me he encontrado con la siguiente recurrencia para obtener los valores de $K_{j}$

\begin {array}{cccccc} 1 & = & K_{1} \tbinom {n+1}{0} \\ 1 & = & K_{1} \tbinom {n+2}{1} & +K_{2} \tbinom {n+2}{0} \\ 1 & = & K_{1} \tbinom {n+3}{2} & +K_{2} \tbinom {n+3}{1} & +K_{3} \tbinom {n+3}{0} \\ 1 & = & K_{1} \tbinom {n+4}{3} & +K_{2} \tbinom {n+4}{2} & +K_{3} \tbinom {n+4}{1} & +K_{4} \tbinom {n+4}{0} \\ & \vdots\\ 1 & = & K_{1} \tbinom {n+j}{j-1} & +K_{2} \tbinom {n+j}{j-2} & +K_{3} \tbinom {n+j}{j-3} & +K_{4} \tbinom {n+j}{j-4} & + \cdots & +K_{j-2} \tbinom {n+j}{2} & +K_{j-1} \tbinom {n+j}{1} & +K_{j} \tbinom {n+j}{0} \end {array}

Es decir, la convolución

$$1=\sum_{i=1}^{j}K_{i}\binom{n+j}{j-i}$$

o dicho de otro modo, si consideramos la secuencia de coeficientes, $K_{1},K_{2},K_{3},\ldots$ el j término viene dado por la recurrencia

$$K_{j}=1-\sum_{i=1}^{j-1}K_{i}\binom{n+j}{j-i}$$

Un cálculo directo da las siguientes soluciones

\begin {array}{cccc} K_{1}= & +1 & = & +1 \\ K_{2}= & -{n+1 \choose 1} & = & - \left ({n+1 \choose 1} \right ) \\ K_{3}= & +{n+2 \choose 2} & = & + \left ({n+1 \choose 2} \right ) \\ K_{4}= & -{n+3 \choose 3} & = & - \left ({n+1 \choose 3} \right ) \\ K_{5}= & +{n+4 \choose 4} & = & + \left ({n+1 \choose 4} \right ) \\ \vdots & \vdots & & \vdots\\ K_{j}= & (-1)^{j-1}{n+j-1 \choose j-1} & = & (-1)^{j-1} \left ({n+1 \choose j-1} \right ) \end {array}

donde ${n \choose i}=\frac{n(n-1)\cdots(n-i+1)}{i!}$ y $\left({N \choose i}\right)=\frac{n(n+1)\cdots(n+i-1)}{i!}$

Sin embargo, esto no demuestra nada.

¿Es posible obtener una solución a partir de la recurrencia inicial (convolución)?

Answer 1

Partimos de la convolución $$1=\sum_{i=1}^j K_i \binom{n+j}{j-i}$$ entonces multiplica ambos lados por $x^{j-1}$ y la suma de $j=1$ a $\infty$ . Para el lado derecho obtenemos $$\sum_{j=1}^\infty \sum_{i=1}^j K_i \binom{n+j}{j-i}x^{j-1}=\sum_{i=1}^\infty \sum_{j=i}^\infty K_i \binom{n+j}{j-i}x^{j-1}$$ donde hemos invertido el orden de la suma. La suma interna sobre $j$ puede entonces reescribirse como $$\sum_{j=i} \binom{n+j}{j-i}x^{j-1}=\sum_{j=0}^\infty\binom{n+i+j}{j}x^{j+i-1} =\frac{x^{i-1}}{(1-x)^{n+i+1}}$$ donde hemos reconocido la serie binomial de exponente negativo $(1-x)^{-n-1}=\sum_{k=0}^\infty\binom{n+k}{k} x^k$ . Completando la suma externa sobre $i$ entonces da la RHS como $$ \sum_{i=1}^\infty K_i \frac{x^{i-1}}{(1-x)^{n+i+1}}=\frac{1}{x (1-x)^{n+1}}\sum_{i=1}^\infty K_i \left(\frac{x}{1-x}\right)^i.$$ Pero el LHS es simplemente la serie geométrica $$\sum_{j=1}^\infty x^{j-1}=1+x+x^2+\cdots=\frac{1}{1-x},$$ y así podemos escribir $$\sum_{i=1}^\infty K_i \left(\frac{x}{1-x}\right)^i=x(1-x)^n.$$ La sustitución $x\mapsto x(1+x)^{-1}$ entonces lleva esto a la forma $$\sum_{i=0}^\infty K_{i+1} x^{i+1}=\frac{x}{(1+x)^{n+1}}=\sum_{i=0}^\infty \binom{n+i}{i} (-1)^i x^{i+1}$$ utilizando la misma serie binomial que antes. Identificando los coeficientes se obtiene finalmente $$K_i = (-1)^{i-1}\binom{n+i-1}{i-1}=(-1)^{i-1}\frac{(n+1)(n+2)\cdots(n+i-1)}{(i-1)!}$$ que es equivalente a la fórmula deducida en el enunciado de la pregunta.