Hallar el enésimo término de una sucesión numérica - Explicación de la pequeña fórmula de Newton

Question

En un libro de problemas de concursos, encontré una referencia a la pequeña fórmula de Newton que se puede utilizar para encontrar el enésima término de una secuencia numérica. Concretamente, se trata de una fórmula basada en las diferencias entre términos consecutivos que se calcula en cada nivel hasta que las diferencias coinciden.

Un ejemplo de aplicación de esta fórmula para calcular el enésima término de la serie (15, 55, 123, 225, 367, 555, 795, ....) consiste en calcular las diferencias como se muestra a continuación:

1) 1st Level difference is (40, 68, 102, 142, 188, 240)
2) 2nd Level difference is (28, 34, 40, 46, 52)
3) 3rd Level difference is (6, 6, 6, 6, 6) 

Ahora el enésimo término es $$15{n-1\choose 0} + 40{n-1\choose 1} + 28{n-1\choose 2} + 6{n-1\choose 3}$$ donde los multiplicadores constantes son el primer término de las diferencias en cada nivel además del primer término de la propia secuencia.

Tras buscar en Internet, no he podido encontrar ninguna referencia a esta fórmula ni una prueba de la misma. Agradecería cualquier explicación sobre este método.

Answer 1

Supongamos que tenemos una secuencia:

$$a_0,a_1,...a_k$$

Y queremos encontrar la función de $n$ que define $a_n$ .

Para ello, empezamos dejando que $a_{n+1}-a_n=\Delta a_n$ y llamamos a esta operación en $a_n$ la diferencia hacia delante. Entonces, dado $\Delta a_n$ podemos encontrar $a_n$ . Suma ambos lados de la ecuación de $n=0$ a $x-1$ y observe que tenemos una serie telescópica:

$$\sum_{n=0}^{x-1} \Delta a_n=\sum_{n=0}^{x-1} (a_{n+1}-a_n)=a_{x}-a_{0}$$

Por lo tanto $a_n=a_0+\sum_{i=0}^{n-1} \Delta a_i$ . También $\Delta a_n=\Delta (0)+\sum_{i=0}^{n-1} \Delta^2 a_n$ ...y así sucesivamente. Usando esto debemos tener si la serie converge:

$$a_n=a_0+\Delta (0) \sum_{x_0=0}^{n-1} 1+\Delta \Delta (0) \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1+\Delta \Delta \Delta (0) \sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} \sum_{x_2=0}^{x_1-1} 1+\cdots$$

Dónde $\Delta^i (0)$ denota el primer término ( $n=0$ ) del $i$ ª secuencia de diferencia de $a_n$ .

Mediante un argumento combinatorio, si tomamos $\Delta^0 (0)=a_0$ y ${n \choose 0}=1$ podemos conseguir:

$$a_n=\sum_{i=0}^{\infty} \Delta^i(0) {n \choose i}$$

Si es el caso desea que la secuencia comience con $a_1$ tenemos que cambiar este resultado a la derecha:

$$a_n=\sum_{i=0}^{\infty} \Delta^i(1) {n-1 \choose i}$$

Tenga en cuenta que al redefinir $a_0$ ser $a_1$ cambiando su índice a la derecha, estás redefiniendo $a_1-a_0=\Delta^1(0)$ ser $a_2-a_1=a_{1+1}-a_{1}=\Delta^1(1)$ .

Answer 2

Empezando por las segundas diferencias tenemos

• $28 = 28$ ,
• $34 = 28 + 6$ ,
• $40 = 28 + 6 + 6$
• $46 = 28 + 6 + 6 + 6$$

Ahora tenemos las primeras diferencias

• $40 = 40$
• $68 = 40 + 28$
• $102 = 40 + 28 + 34 = 40 + 28 + (28 + 6)$
• $142 = 40 + 28 + 34 + 50 = 40 + 28 + (28 + 6) + (28 + 6 + 6)$

Así pues, la secuencia original es

• $15 = 15$
• $55 = 15 + 40$
• $123 = 15 + 40 + 68 = 15 + 40 + [40 + 28]$
• $225 = 15 + 40 + 68 + 102 = 15 + 40 + [40 + 28] + [40 + 28 + (28 + 6)]$
• \begin{align} 367 &= 15 + 40 + 68 + 102 + 142 \\ &= 15 + 40 + [40 + 28] + [40 + 28 + (28 + 6)] + [40 + 28 + (28 + 6) + (28 + 6 + 6)] \end{align}

Los patrones deben ser claros. Así que cuenta cuántos 15, 40, 28 y 6 hay en cada término.