Recurrencia lineal no homogénea de primer orden para la suma

Question

Recurrencia lineal no homogénea de primer orden para la suma

Matemáticas
Matemáticas discretas
relaciones de recurrencia

Aeryk

He estado estudiando recurrencias lineales en el caso no homogéneo, pero me he quedado atascado con el siguiente problema: encontrar una forma cerrada para $s_n=\sum_{i=1}^n i$ . Sé que la respuesta es $n(n+1)/2$ por otros métodos, pero parece que no puedo obtener la respuesta correcta usando los métodos de recursión.

Aquí está mi intento: la secuencia satisface la recurrencia no homogénea $s_n-s_{n-1}=n$ . Así que considere la recurrencia homogénea asociada $\overline{s_n}-\overline{s_{n-1}}=0$ . Esto obviamente tiene solucion $\overline{s_n}=C_1$ por alguna constante $C_1$ .

A continuación, tratamos de encontrar una solución particular. Dado que la parte no homogénea es lineal, debemos suponer $s^{(p)}_n = A n+B$ para constantes $A$ y $B$ . Pero luego, sustituyendo de nuevo en la recurrencia original, da $(An+B)-(A(n-1)+B) = A$ . Es imposible para la constante $A$ para igualar la variable $n$ . Y entonces estoy atascado.

Supongo que debería haber probado una solución particular que fuera cuadrática, pero en todos los libros que he visto, la solución particular tiene un grado igual a la parte no homogénea.

Entonces, ¿qué estoy haciendo mal?

Hizo

"Usar el método de recursión" significa mostrar que

s_{0} = 0 (0 + 1) / 2

$s_0=0(0+1)/2$ y eso si

s_{n} = n (n + 1) / 2

$s_n=n(n+1)/2$ entonces

s_{n + 1} = (n + 1) (n + 2) / 2

$s_{n+1}=(n+1)(n+2)/2$ . El enfoque que explica simplemente pospone la resolución de la recursividad al segundo paso cuando se busca una solución particular.

Aeryk

@Did: Creo que estás confundiendo una prueba de inducción con el método para resolver relaciones de recurrencia. quiero llegar a

s_{n} = n (n + 1) / 2

$s_n=n(n+1)/2$ usando métodos similares a: eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/…

Hizo

Enviarme notas sobre soluciones de relaciones de recurrencia lineal es dulce, soy muy sensible a la atención ... Más en serio, ¿cómo llamas a los métodos de recursión ?

Aeryk

El método al que me refiero es el método en el que forma su solución como una solución homogénea más una solución particular.

Hizo

No estoy seguro de que alguien llame a esto un método de recursión... De todos modos, en el presente caso, como expliqué en mi primer comentario , esto es un callejón sin salida porque informa todo el trabajo para encontrar una solución particular.

Aeryk

¿Preferiría "usar la teoría de las relaciones de recurrencia lineal"? El punto es: ¿Cómo encuentra la solución que dio en su comentario inicial? Muéstrame los pasos para que pueda aplicarlo a casos más difíciles.

Hizo

Correcto, ahora que su terminología confusa está fuera del camino, volvamos a las matemáticas: si

s_{n} - s_{n - 1} = p (n)

$s_n-s_{n-1}=p(n)$ entonces

s_{n} = s_{0} + q (n)

$s_n=s_0+q(n)$ con

q (n) = p (1) + p (2) + \dots + p (n)

$q(n)=p(1)+p(2)+\cdots+p(n)$ . Si

p

$p$ es un polinomio de grado

k

$k$ , entonces

q

$q$ es un polinomio de grado

k + 1

$k+1$ . Encontrar

q

$q$ cuando

p (n) = n

$p(n)=n$ , uno puede intentar

s_{n} = 1

$s_n=1$ (pero entonces

s_{n} - s_{n - 1} = 0

$s_n-s_{n-1}=0$ , no es interesante),

s_{n} = n

$s_n=n$ (entonces

s_{n} - s_{n - 1} = 1

$s_n-s_{n-1}=1$ ) y

s_{n} = n^{2}

$s_n=n^2$ (entonces

s_{n} - s_{n - 1} = 2 n - 1

$s_n-s_{n-1}=2n-1$ ) por lo tanto una combinación lineal de

s_{n} = n^{2}

$s_n=n^2$ y

s_{n} = n

$s_n=n$ trabajará. Si

s_{n} - c s_{n - 1} = p (n)

$s_n-cs_{n-1}=p(n)$ y

c \neq 1

$c\ne1$ entonces

s_{n}

$s_n$ polinomio de grado

k

$k$ obras. ...

Hizo

... Un escenario más teórico es notar que la transformada

L

$L$ definido por

(L p) (X) = p (X) - p (X - 1)

$(Lp)(X)=p(X)-p(X-1)$ en

K [X]

$K[X]$ es lineal con el kernel

K_{0} [X]

$K_0[X]$ y

L (K_{k + 1} [X]) = K_{k} [X]

$L(K_{k+1}[X])=K_{k}[X]$ para cada

k

$k$ . Del mismo modo, si

c \neq 1

$c\ne1$ ,

L

$L$ definido por

(L p) (X) = p (X) - c p (X - 1)

$(Lp)(X)=p(X)-cp(X-1)$ en

K [X]

$K[X]$ es lineal con el kernel

{0}

$\{0\}$ y

L (K_{k} [X]) = K_{k} [X]

$L(K_{k}[X])=K_{k}[X]$ para cada

k

$k$ . Los resultados anteriores siguen.

Aeryk

Entonces, solo para verificar, entiendo que cuando una recurrencia lineal no homogénea de primer orden tiene la recurrencia lineal homogénea asociada

s_{n} - s_{n - 1} = 0

$s_n-s_{n-1}=0$ , es un caso especial en el que la solución particular (de hecho, la solución) no se parece a la parte no homogénea. Pero entonces esto plantea la pregunta: ¿y si

s_{n} - s_{n - 1} = \sin (n)

$s_n-s_{n-1}=\sin(n)$ o algún otro no polinomio. ¿Cuál es entonces el método general?

Hizo

Cuando el RHS es

n

$n$ , la solución particular se parece a la RHS. Cuando el RHS es

\sin n

$\sin n$ , jugando con

\cos n

$\cos n$ y

\sin n

$\sin n$ muestra una solución es una combinación lineal de estos, que se parece a la RHS. En general, una solución de

s_{n} - s_{n - 1} = p (n)

$s_n-s_{n-1}=p(n)$ es

s_{n} = q (n)

$s_n=q(n)$ con

q (n) = p (n) + \dots + p (1)

$q(n)=p(n)+\cdots+p(1)$ , como ya se mencionó.

Respuestas (2)

Recurrencia lineal no homogénea de primer orden para la suma

"Usar el método de recursión" significa mostrar que $s_0=0(0+1)/2$ y eso si $s_n=n(n+1)/2$ entonces $s_{n+1}=(n+1)(n+2)/2$ . El enfoque que explica simplemente pospone la resolución de la recursividad al segundo paso cuando se busca una solución particular.
@Did: Creo que estás confundiendo una prueba de inducción con el método para resolver relaciones de recurrencia. quiero llegar a $s_n=n(n+1)/2$ usando métodos similares a: eecs.yorku.ca/course_archive/2008-09/S/1019/Website_files/…
Enviarme notas sobre soluciones de relaciones de recurrencia lineal es dulce, soy muy sensible a la atención ... Más en serio, ¿cómo llamas a los métodos de recursión ?
El método al que me refiero es el método en el que forma su solución como una solución homogénea más una solución particular.
No estoy seguro de que alguien llame a esto un método de recursión... De todos modos, en el presente caso, como expliqué en mi primer comentario , esto es un callejón sin salida porque informa todo el trabajo para encontrar una solución particular.
¿Preferiría "usar la teoría de las relaciones de recurrencia lineal"? El punto es: ¿Cómo encuentra la solución que dio en su comentario inicial? Muéstrame los pasos para que pueda aplicarlo a casos más difíciles.
Correcto, ahora que su terminología confusa está fuera del camino, volvamos a las matemáticas: si $s_n-s_{n-1}=p(n)$ entonces $s_n=s_0+q(n)$ con $q(n)=p(1)+p(2)+\cdots+p(n)$ . Si $p$ es un polinomio de grado $k$ , entonces $q$ es un polinomio de grado $k+1$ . Encontrar $q$ cuando $p(n)=n$ , uno puede intentar $s_n=1$ (pero entonces $s_n-s_{n-1}=0$ , no es interesante), $s_n=n$ (entonces $s_n-s_{n-1}=1$ ) y $s_n=n^2$ (entonces $s_n-s_{n-1}=2n-1$ ) por lo tanto una combinación lineal de $s_n=n^2$ y $s_n=n$ trabajará. Si $s_n-cs_{n-1}=p(n)$ y $c\ne1$ entonces $s_n$ polinomio de grado $k$ obras. ...
... Un escenario más teórico es notar que la transformada $L$ definido por $(Lp)(X)=p(X)-p(X-1)$ en $K[X]$ es lineal con el kernel $K_0[X]$ y $L(K_{k+1}[X])=K_{k}[X]$ para cada $k$ . Del mismo modo, si $c\ne1$ , $L$ definido por $(Lp)(X)=p(X)-cp(X-1)$ en $K[X]$ es lineal con el kernel $\{0\}$ y $L(K_{k}[X])=K_{k}[X]$ para cada $k$ . Los resultados anteriores siguen.
Entonces, solo para verificar, entiendo que cuando una recurrencia lineal no homogénea de primer orden tiene la recurrencia lineal homogénea asociada $s_n-s_{n-1}=0$ , es un caso especial en el que la solución particular (de hecho, la solución) no se parece a la parte no homogénea. Pero entonces esto plantea la pregunta: ¿y si $s_n-s_{n-1}=\sin(n)$ o algún otro no polinomio. ¿Cuál es entonces el método general?
Cuando el RHS es $n$ , la solución particular se parece a la RHS. Cuando el RHS es $\sin n$ , jugando con $\cos n$ y $\sin n$ muestra una solución es una combinación lineal de estos, que se parece a la RHS. En general, una solución de $s_n-s_{n-1}=p(n)$ es $s_n=q(n)$ con $q(n)=p(n)+\cdots+p(1)$ , como ya se mencionó.

Marty Cohen · Answer 1

La cosa es que quieres la diferencia $s_n-s_{n-1}$ ser $n$ , un polinomio de grado uno .

Algo que deberías, hacer o sabrás es que la primera diferencia de un polinomio de grado $m$ es un polinomio de grado $m-1$ .

Por lo tanto, para hacer que la diferencia de un polinomio tenga grado $1$ , el polinomio tiene que ser de grado $2$ .

Una vez que veas esto, el resto debería ser relativamente rutinario.

¿Es esto sólo un caso especial entonces? Si tuviera $s_n-2s_{n-1}=n$ entonces la solución particular sería simplemente lineal.

Aeryk · Answer 2

Encontré la respuesta/explicación en "Matemáticas discretas y combinatorias" de Grimaldi. Primero da la regla general:

[I] un sumando $f_1(n)$ de $f(n)$ es un múltiplo constante de una solución de la relación homogénea asociada... multiplicamos la solución particular $a_{n_1}^{(p)}$ correspondiente a $f_1(n)$ por la mínima potencia de $n$ , decir $n^s$ , para el cual no hay sumando de $n^s f_1(n)$ es una solución de la relación homogénea asociada.

Luego pasa a demostrar esto en el caso $a_{n+1}-a_n=n$ :

Podríamos pensar que la solución particular es $A_1n+A_0$ para constantes $A_0$ y $A_1$ . Pero aquí la relación homogénea asociada es $a_{n+1}=a_n$ . ... Por lo tanto, el sumando $A_0$ es una solución de la relación homogénea asociada. En consecuencia, la [regla] anterior nos dice que debemos multiplicar $A_1n+A_0$ por la mínima potencia de $n$ para el cual ya no tenemos ningún sumando constante. Esto se logra multiplicando $A_1n+A_0$ por $n^1$ , y así encontramos aquí que
$a_{norte}^{(pag)} = A_{1} {norte}^{2} + A_{0} norte .$ $a_n^{(p)}=A_1n^2+A_0n.$

Recurrencia lineal no homogénea de primer orden para la suma

Aeryk

Hizo

Aeryk

Hizo

Aeryk

Hizo

Aeryk

Hizo

Hizo

Aeryk

Hizo

Respuestas (2)

Marty Cohen

Aeryk

Aeryk

Prueba de inducción de una relación de recurrencia?

Demostrar el número de adiciones del algoritmo del número de Fibonacci

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Relación de recurrencia an+2=3an+1−2anan+2=3an+1−2ana_{n+2}=3a_{n+1}-2a_n

Conjuntos "gruesos" de enteros y números de Fibonacci

Encontrar una relación de recurrencia sobre un diccionario dado

Prueba combinatoria de x(n)=∑nk=1L(n,k)(x)kx(n)=∑k=1nL(n,k)(x)kx^{(n)} = \sum_{k = 1}^n L(n,k)(x)_k

Cómo resolver la relación de recurrencia a continuación

Pasar de una función generadora racional a una relación de recurrencia

Pregunta sobre la técnica de Graham, Knuth y Patashnik para convertir recurrencias de primer orden en sumatorias