Desconcertado por la resolución de la lista de números de

Question

Mi hijo de Matemáticas de la tarea tiene que ver con el número de patrones/secuencias. "¿Cuál es el enésimo término?". Lo que él había hecho muy bien, pero la última secuencia fue algo como esto:

19,77,265,715,1607,3169

Él estaba decidida a que él no tenía una técnica para solucionar esto, y que debe ser un "falso" pregunta. Sin embargo, algo sobre el número parecía como que podría ser un patrón así que hice un poco de investigación.

Los puse en una hoja de cálculo y encontrar las diferencias entre números consecutivos:

58, 188, 450, 892, 1562

Sin pistas. Me decidí a encontrar las diferencias de esta lista:

130, 262, 442, 670

Ellos parecen ser cada vez menos interesantes con cada paso:

132, 180, 228

Entonces:

48, 48

Me di cuenta de que podía generar una lista como esta mediante una fórmula:

$$\begin{align}ax^n+bx^p+cx^q+dx+y\end{align}$$

Puedo tener muchos términos del poder de los que me gustan, pero la diferencia siempre se resuelve después de un número de pasos igual a la máxima potencia.

¿Alguien puede explicar qué está sucediendo aquí, por favor? Yo no soy un Matemático, así que por favor mantenerlo tan simple como sea posible.

Answer 1

Lo que se computing es un binomio de transformación (ver en Wikipedia o MathWorld)

Si su secuencia original es $u_0,\dots,u_n$, calcular las sucesivas diferencias de su lista, y mantener sólo el primer término de estas diferencias.

Las diferencias son

$$\begin{matrix} 19 & 77 & 265 & 715 & 1607 & 3169\\ 58 & 188 & 450 & 892 & 1562\\ 130 & 262 & 442 & 670\\ 132 & 180 & 228\\ 48 & 48\\ 0 \end{de la matriz}$$

Así que la lista de primeros términos es $(v_k)=(19,58,130,132,48)$, con último término distinto de cero, siendo en este caso $v_4=48$, y a continuación, puede escribir, con $m=4$,

$$u_n=\sum_{k=0}^{m} {n \choose k}v_k$$

Que es

$$u_n=19{n \elegir 0}+58{n \elegir 1}+130{n \elegir 2}+132{n \elegir 3}+48{n \elegir 4}\\ =2n^4+10n^3+21n^2+25n+19$$

Y por medio de este método, el siguiente término es $u_6=5677$.

Ahora, la razón por la que esto funciona es que, dada una secuencia $u_n$, si se define, para todos los $n\geq0$,

$$v_n=(-1)^n\sum_{k=0}^n (-1)^k{n \choose k}u_k$$

Entonces, para todos los $n\geq0$,

$$u_n=\sum_{k=0}^n {n \choose k}v_k$$

No voy a dar una prueba, ya que desea mantener las cosas simples, pero al menos se puede ver que la primera suma. Si calcula el primer término de las sucesivas diferencias de $u_n$, se tiene:

$$u_0$$ $$u_1-u_0$$ $$(u_2-u_1)-(u_1-u_0)=u_2-2u1+u_0$$ $$(u_3-2u_2+u_1)-(u_2-2u_1+u_0)=u_3-3u_2+3u_1-u_0$$ $$(u_4-3u_3+3u_2-u_1)-(u_3-3u_2+3u_1-u_0)=u_4-4u_3+6u_2-4u_1+u_0$$

Y usted debería ver un patrón.

También, desde

$${n \choose k}=\frac{n(n-1)\cdots(n-k+1)}{k!}$$

De esta manera, puede escribir su segunda suma como un polinomio en $n$.

---

Una característica interesante de binomio de transformación es que si usted secuencia original es un polinomio de grado $m$, luego de las sucesivas diferencias desaparecen después de que el $m$th, y recuperar su polinomio en términos de los coeficientes binomiales (es solo un cambio de base).

Otra forma de ver esto es que si usted tiene una secuencia finita (de longitud $m$), se puede calcular todas las posibles diferencias, que es de hasta el $(m-1)$th, y asumiendo que todas las siguientes diferencias sería cero, reconstruir la interpolación polinómica $P$ (luego de grado $m-1$), de tal manera que $P(0)$ es le primer término, $P(1)$ el segundo, etc. Es una forma práctica de calcular el polinomio de interpolación de cuando absissas son enteros $0,1,\dots m-1$. Aviso que es un caso especial de Newton interpolación.

Escribí que con una lista de longitud $m$ usted obtiene un polinomio de grado $m-1$, en realidad es de grado en la mayoría de las $m-1$. Usted puede haber notado que, en su caso, la última diferencia es cero, por lo que el polinomio tiene grado $m-2=4$.

---

Al ver una pregunta, usted puede realmente responder a cualquier número que usted desea para el siguiente, como siempre se puede (al menos) encontrar un polinomio de interpolación de que le daría a este número. Por ejemplo, usted sólo tiene que añadirlo a su lista, y calcular el binomio transformar con la ampliación de la lista, para recuperar un nuevo polinomio. Por supuesto, no es lo que se espera, pero tal ejercicio no es muy interesante, desde el punto de vista matemático.

Sin embargo, lo que sucede en la práctica que tenemos una secuencia que desea identificar, y el binomio transformación puede ser extremadamente útil para encontrar un patrón, aunque no funciona en todos los casos. Y otra herramienta muy útil es OEIS. Es sólo una base de datos, pero es un gran uno.

Answer 2

Supongamos que se nos ha dado ninguna "patrón" de $n$ números

$$c_1,c_2,\cdots,c_n$$

Así, en el ejemplo de $n=6$$c_1=19, c_2=77, \cdots$.

Entonces, lo que básicamente se han descubierto es el hecho de que siempre podemos encontrar una "regla" en la forma de un polinomio de grado en la mayoría de las $n-1$,

$$P(x)=a_{n-1}x^{n-1}+\cdots+a_1 x+a_0$$

tal que $P(1)=c_1, P(2)=c_2, \dots, P(n)=c_n$.

Las razones por la que esto funciona es simple: Estamos buscando la $n$ coeficientes de $a_{n-1},\dots a_0$ de manera tal que el $n$ ecuaciones $P(k)=c_k$ $k=1,\dots,n$ son verdaderas. Que es que estamos resolviendo un sistema de $n$ ecuaciones lineales:

$$\left\{\begin{array}{ll} a_{n-1} 1^{n-1} +& \cdots +& a_1 1^1 +& a_0 1^0 &= c_1\\ a_{n-1} 2^{n-1} +& \cdots +& a_1 2^1 +& a_0 2^0 &= c_2\\ a_{n-1} 3^{n-1} +& \cdots +& a_1 3^1 +& a_0 3^0 &= c_3\\ \vdots & \cdots & \vdots & \vdots & \vdots\\ a_{n-1} n^{n-1} +& \cdots +& a_1 n^1 +& a_0 n^0 &= c_n\\ \end{array}\right.$$

Así que tenemos $n$ ecuaciones y $n$ incógnitas. De la escuela, usted puede recordar que, en tal situación, usted puede esperar para encontrar una solución para su incógnitas (a menos que las ecuaciones contienen "contradicciones").

El matemáticamente precisa razón por la que la solución puede ser encontrar aquí es que la matriz de coeficientes (que casualmente tiene un nombre y se conoce como la matriz de Vandermonde) es invertible. Por lo tanto, no existe un único y determinado polinomio de grado menor-igual $n-1$ dando la "regla" para el "patrón".

El esquema de la diferencia que usted le dio es una manera de resolver este sistema de ecuaciones.

Answer 3

Para su INFORMACIÓN, usted puede encontrar fácilmente una ecuación polinómica que se ajusta a esa secuencia en Excel. Esto probablemente no es lo que el maestro está buscando, pero es realmente fácil.

1. Pegar los números en una columna en Excel.

2. Resaltar las celdas y insertar un gráfico de dispersión

3. Haga clic en un punto y haga clic en "Agregar línea de Tendencia..."

4. Compruebe la Pantalla "Ecuación" y "Mostrar R-squared" casillas de verificación.

5. Haga clic en la regresión tipos y jugar con los insumos hasta que el R-cuadrado es igual a 1.

Tengo una ecuación de ajuste de la tendencia del tipo de Polinomio y la orden de 4. La ecuación es:

y = 2x^4 + 2x^3 + 3x^2 + 5x + 7

El siguiente valor es 5677 que está de acuerdo con su conjetura. Esto se siente como hacer trampa, aunque.

Answer 4

Supongamos que tenemos alguna secuencia generada por la evaluación de un polinomio $$P(x)=a_n x^n+a_{n-1}x^{n-1}+\cdots+ a_1 x+a_0$$ at integers $x=0,1,2,3,$, etc. ¿Qué podemos esperar sobre su secuencia de consecutivos diferencias? Si tomamos la diferencia entre el $x$-ésimo término y el $(x+1)$-ésimo término, y organizar por los coeficientes, tenemos

$$P(x+1)-P(x)=a_n((x+1)^n-x^n)+a_{n-1}((x+1)^{n-1}-x^{n-1})+\cdots+a_0((x+1)-x)$$ Este es un lugar complicado de expresión, pero hay una observación clave. Supongamos que realizar la (tedioso) multiplicación involucrados en la expansión de una expresión como $(x+1)^n-x^n$: entonces, el término se $x^n$ serán cancelados, y vamos a quedar con algunos (complicado) polinomio de la forma $$P'(x)=a'_{n-1}x^{n-1}+a'_{n-2}x^{n-2}+\cdots +a'_1 x+a_0'.$$

La implicación se puede extraer es que, si empezamos con una secuencia generada por un polinomio con líderes plazo $x^n$, y luego tomar las diferencias nos da una nueva secuencia generado por un polinomio con líderes plazo $x^{n-1}$. Esto es genial ya que se puede repetir esto: Si repetimos este proceso un total de $n$ tiempos, vamos a terminar con una secuencia que es constante (tal vez con el líder término es diferente que el resto.)

Para aplicar esto a su problema, tenga en cuenta que hemos tenido que llevar a cabo cuatro 'diferencias' de su hijo de la secuencia para llegar a una constante. Por lo tanto, la secuencia es generado por algún polinomio $P(x)=a x^4+b x^3+c x^2+d x+f$ como se llegó a la conclusión.

Answer 5

Me gustaría publicar esto como un comentario, pero no tienen la reputación de permitir que ...

Zurdo, te comento que usted pensaba que iba a encontrar este tipo de técnica útil en la práctica ... bueno, ok, pero ...

Ten en cuenta que el uso de este método, el siguiente número puede ser cualquier cosa que quieras ! es decir, levantar ningún valor en absoluto como el 7 de término de la serie, y usted será capaz de obtener un polinomio que los partidos y los primeros 6 números demasiado, esta vez utilizando un polinomio que va a algo más veces x^6.

Por desgracia, en los problemas prácticos, utilizando largo polinomios para que coincida con los datos reales es casi siempre una mala jugada, a menos que haya algún indicio de que el proceso subyacente de la que realmente no siga un determinado tiempo polinomial. Es un método que se parecen funcionar muy bien para un rato, pero luego se caen a pedazos por completo cuando menos te lo esperas.