Encontrando el término "n" de una secuencia por el método de la diferencia

Question

Consideremos $$S_n=t_1+t_2+...+t_n$$ y sea $_{t_1}=t_2-t_1,_{t_2}=t_3-t_2,...,_{t_{n-1}}=t_n-t_{n-1}$ la primera diferencia de orden.

De manera similar $^2_{t_1}=_{t_2}-_{t_1},...^2_{t_{n-2}}=_{t_{n-1}}-_{t_{n-2}}$ será la segunda diferencia de orden.

De manera similar calculamos $^{n-1}_{t_1}$.

La pregunta es demostrar que $$t_n=t_1+\binom{n-1}{1} _{t_1}+\binom{n-1}{2}^2_{t_1}+...+^{n-1}_{t_1}$$

Intenté verificarlo para casos simples e intenté probarlo por inducción pero no pude continuar. ¿Algún idea?

Answer 1

Puedes demostrarlo por inducción pero no será muy divertido. Aquí tienes una demostración mucho más limpia.

Considera el operador de desplazamiento $S$, que toma como entrada una secuencia $t_n$ y devuelve como salida una nueva secuencia

$$(St)_n = t_{n+1}.$$

El operador de desplazamiento puede usarse para escribir el operador de diferencia hacia adelante

$$(\Delta t)_n = t_{n+1} - t_n = \left( (S - 1) t \right)_n$$

donde $1$ denota el operador de identidad, que envía una secuencia $t_n$ a $t_n$, y $S - 1$ es la suma de operadores. La clave del enfoque que estoy a punto de describir es que es posible realizar álgebra en operadores: puedes sumarlos sumándolos punto por punto, y multiplicarlos componiéndolos. Por ejemplo, la segunda diferencia es

$$(\Delta^2 t)_n = (t_{n+2} - t_{n+1}) - (t_{n+1} - t_n) = t_{n+2} - 2 t_{n+1} + t_n$$

y es posible ver esto directamente en términos de operadores calculando

$$\Delta^2 = (S - 1)^2 = S^2 - 2S + 1.$$

Repetir este argumento para exponentes mayores da

$$\Delta^k = (S - 1)^k = \sum_{i=0}^k (-1)^i {k \choose i} S^i$$

¡simplemente utilizando el teorema binomial! Traducido a secuencias, esto significa

$$\boxed{ (\Delta^k t)_n = \sum_{i=0}^k (-)^i {k \choose i} t_{n+i} }.$$

Pero queremos ir en la dirección contraria: expresar el desplazamiento $S^n$ en términos del operador de diferencia. Pero dado que $\Delta = S - 1$, tenemos $S = \Delta + 1$, y por lo tanto

$$S^k = (\Delta + 1)^k = \sum_{i=0}^k {k \choose i} \Delta^i$$

entonces, aplicado a secuencias, esto da

$$\boxed{ t_{n+k} = \sum_{i=0}^k {k \choose i} (\Delta^i t)_n }.$$

Esta es la identidad deseada, reindexada un poco.

Answer 2

NOTA: ESTA NO ES UNA RESPUESTA COMPLETA.

Así que comienzo con \begin{align} ^{n-1}_{t_{1}}&=^{n-2}_{t_2}-^{n-2}_{t_1}\\ &=^{n-3}_{t_3}-^{n-3}_{t_2}-^{n-3}_{t_2}+^{n-3}_{t_1}\\ &=^{n-3}_{t_3}-2^{n-3}_{t_2}+^{n-3}_{t_1}\\ &=^{n-4}_{t_4}-^{n-4}_{t_3}-2^{n-4}_{t_3}+2^{n-4}_{t_2}+^{n-4}_{t_2}-^{n-4}_{t_1}\\ &=^{n-4}_{t_4}-3^{n-4}_{t_3}+3^{n-4}_{t_2}-^{n-4}_{t_1}\\ \end{align>

Así que el patrón de coeficiente binomial con signos alternos similares a los de $(a-b)^k$ es bastante claro aquí. Podemos usar la inducción para verificarlo, pero lo dejaré por ahora. Así que tenemos \begin{align> ^{n-1}_{t_{1}}&=(-1)^0{k \choose 0}^{n-(k+1)}_{t_{k+1}}+(-1)^1{k \choose 1}^{n-(k+1)}_{t_{(k+1)-1}}+\dots+(-1)^k{k \choose k}^{n-(k+1)}_{t_{(k+1)-k}}\\ &=(-1)^0{k \choose 0}^{n-(k+1)}_{t_{k+1}}+(-1)^1{k \choose 1}^{n-(k+1)}_{t_{(k+1)-1}}+\dots+(-1)^k{k \choose k}^{n-(k+1)}_{t_{1}}\\ &=\sum_{r=0}^{k}{(-1)^r}{k \choose r}{^{n-(k+1)}_{t_{k-r+1}}} \end{align>

Ahora fijaré $k=n-1$, entonces tenemos \begin{align> ^{n-1}_{t_{1}}&=\sum_{r=0}^{n-1}{(-1)^r}{n-1 \choose r}{t_{n-r}} Así que en general, tenemos \begin{align> ^{n-m}_{t_{1}}&=\sum_{r=0}^{n-m}{(-1)^r}{n-m \choose r}{t_{n-m-r+1}}\\ {{n-1} \choose{n-m}}^{n-m}_{t_{1}}&=\sum_{r=0}^{n-m}{(-1)^r}{{n-1} \choose{n-m}}{n-m \choose r}{t_{n-m-r+1}} La expresión del lado derecho de la expresión dada es \begin{align> \sum_{m=1}^{n-1}{{n-1} \choose{n-m}}^{n-m}_{t_{1}}&=\sum_{m=1}^{n-1}\sum_{r=0}^{n-m}{(-1)^r}{{n-1} \choose{n-m}}{n-m \choose r}{t_{n-m-r+1}} He intentado cambiar el índice pero hasta ahora mis intentos tampoco han tenido éxito.

Answer 3

Aquí mostramos por inducción lo siguiente es válido para $n\geq 1$

\begin{align*} t_n=\sum_{j=0}^{n-1}\binom{n-1}{j}\Delta_{t_1}^j\tag{1} \end{align*}

Note que adicionalmente establecemos $\Delta_{t_1}^0:=t_1$.

Paso base: $n=1$

El lado derecho de (1) evaluado en $n=1$ es \begin{align*} \sum_{j=0}^{0}\binom{0}{j}\Delta_{t_1}^j =\binom{0}{0}\Delta_{t_1}^0=t_1 \end{align*> y el paso base sigue.

Hipótesis de inducción: Asumimos la validez de (1)

Paso de inducción: $n\rightarrow n+1$

Tenemos que mostrar \begin{align*}> t_{n+1}=\sum_{j=0}^{n}\binom{n}{j}\Delta_{t_1}^j \end{align*}

Comenzamos con el lado derecho y obtenemos \begin{align*}> \color{blue}{\sum_{j=0}^{n}\binom{n}{j}\Delta_{t_1}^j } &=\binom{n}{0}\Delta_{t_1}^0+\sum_{j=1}^{n-1}\binom{n}{j}\Delta_{t_1}^j+\binom{n}{n}\Delta_{t_1}^n\tag{2}\\ &=\Delta_{t_1}^0+\sum_{j=1}^{n-1}\left[\binom{n-1}{j}+\binom{n-1}{j-1}\right]\Delta_{t_1}^j+\Delta_{t_1}^n\tag{3}\\ &=\Delta_{t_1}^0+\sum_{j=1}^{n-1}\binom{n-1}{j}\Delta_{t_1}^j+\sum_{j=0}^{n-2}\binom{n-1}{j}\Delta_{t_1}^{j+1}+\Delta_{t_1}^n\tag{4}\\ &=\sum_{j=0}^{n-1}\binom{n-1}{j}\Delta_{t_1}^{j}+\sum_{j=0}^{n-1}\binom{n-1}{j-1}\Delta_{t_1}^{j+1}\tag{5}\\ &=\left(1+\Delta_{t_1}\right)\sum_{j=0}^{n-1}\binom{n-1}{j}\Delta_{t_1}^{j}\tag{6}\\ &=(1+\Delta_{t_1})t_n\tag{7}\\ &=t_n+t_{n+1}-t_n\\ &\color{blue}{=t_{n+1}} \end{align*}> y la afirmación sigue.

Comentario:

• En (2) dividimos el primer y último elemento como preparación para el siguiente paso.

• En (3) usamos la identidad binomial $\binom{n}{j}=\binom{n-1}{j}+\binom{n-1}{j-1}$.

• En (4) dividimos las sumas y desplazamos el índice de la suma derecha para empezar con $j=0$.

• En (5) fusionamos los términos individuales en las sumas.

• En (6) factorizamos la suma y estamos listos para usar la hipótesis de inducción en el siguiente paso (7).

Nota: Para ver mejor la conexión con la respuesta de @QiaochuYuan, observe que también podemos escribir la relación (1) como

\begin{align*}> t_n=(1+\Delta_{t_1})^{n-1} \end{align*}

y el paso de inducción $n\rightarrow n+1$ en esta notación simplemente se convierte en

\begin{align*}> \color{blue}{(1+\Delta_{t_1})^n}=(1+\Delta_{t_1})(1+\Delta_{t_1})^{n-1}=(1+\Delta_{t_1})t_n\color{blue}{=t_{n+1}} \end{align*}>

indicando la fuerza y elegancia del enfoque basado en el operador, además de la visión adicional \begin{align*}> (\Delta+1)^n=S^n\qquad\Longleftrightarrow\qquad (S-1)^n=\Delta^n \end{align*}>

Answer 4

La respuesta de Qiaochu Yuan es excelente, pero quería contribuir con un método alternativo.

Podemos construir un polinomio $f(x)$ tal que $f(k) = t_{k+1}$.

La fórmula de diferencias hacia adelante de Newton nos dice que

$$f(x + a) = \sum_{k=0}^\infty \binom{a}{k} \Delta^k f(x)$$

Su conjetura se prueba simplemente tomando $x = 0$ y $a = n - 1$.