UBACS UBA - CienciaS · Foro de Alumnos

Tema

[No Resuelto](17/10/05) Tema 1 - Ej 3

6 respuestas 8910 visitas
#1 Cloud
$$\textrm{Sea $(a_n)_{n\geq 0}$ la sucesion {d}efinida inductivamente por}$$
$$a_0=1,a_1=3,a_n=a_{n-1}-a_{n-2}(n\geq2)$$
$$\textrm{i)Probar que $a_{n+6}=a_n$ para todo $n\geq0$}$$
$$\textrm{Calcular $\sum_{k=0}^{255}a_k$}$$

AYUDA!!!!!! 😛
y gracias

Firma

111dz1.gif

#2 Yossarian

Bien, como exequiel se va a encargar de postear una resolución razonable en un rato, yo postéo una más sui generis. Utilizo álgebra del CBC a full, pero nada demasiado complicado ni largo.

Fijate que la recurisión depende únicamente de los dos términos anteriores para construirse el siguiente, y que lo que hace es armarse una combinación lineal de los dos términos anteriores. Entonces, podés hacer el siguiente truquito. Te armás la matriz

$$A = \left(\begin{matrix}1 & -1 \ 1 & 0\end{matrix}\right)$$
. Entonces, tenés, oh maravilla, que
$$A \cdot \left(\begin{matrix}a_n \ a_{n-1}\end{matrix}\right) = \left(\begin{matrix}a_{n+1} \ a_n\end{matrix}\right)$$
. Fijate que de eso se deduce que si hacés
$$A^n \cdot \left(\begin{matrix}a_1 \ a_0\end{matrix}\right) = \left(\begin{matrix}a_{n+1} \ a_n\end{matrix}\right)$$
. Lo que sigue es una técnica estándar para encontrar términos generales para recurrencias "lindas". Es una de las aplicaciones más simpáticas del álgebra lineal.

Ahora, si le calculamos el polinomio característico a la matriz (recuerden que eso se hacía tomando el determinante \(\det(A - X \cdot I)\)), donde I es la matriz identidad, y nos da \(X^2 - X +1\). Este polinomio tiene dos raices distintas, no nulas, así que la matriz es diagonalizable: tenemos una matriz \(C\), inversible, tal que

$$C \cdot A \cdot C^{-1} = \left(\begin{matrix}w_1 & 0 \ 0 & w_2\end{matrix}\right) = B$$
. Ejercicio, ver que
$$(C \cdot A \cdot C^{-1})^n = C \cdot A^n \cdot C^{-1} = \left(\begin{matrix}w_1^n & 0 \ 0 & w_2^n\end{matrix}\right)$$
, donde \(w_1, w_2\) son las raíces del polinomio. En particular, si \(B^6 = I\), tenemos que \((C \cdot A \cdot C^{-1})^6 = C \cdot A^6 \cdot C^{-1} = B^6 = I\), y eso dice que \(A^6 = I\), es decir, que aplicar seis veces la transformación nos devuelve nuestro par original, y la sucesión arranca otra vez (punto fundamental), que es lo que necesitamos.

Un tiempo de cancha con \(G_n\) lo hace a uno decir "Oh, maravilla, \(X^2 - X +1 \mid X^6-1\)". La manera de convencerse es factorizar \(X^6-1\), que no es tan difícil como parece a primera vista, y ver que ese polinomio aparece entre los factores. Eso quiere decir que las raices del polinomio característico son raíces sextas de la unidad... es decir, que elevadas a la sexta dan 1, que es justo lo que necesitamos (obviamente, me di cuenta primero de que me convenía que las raíces fueran raices sextas, y después vi que el polinomio servía) QED.

Ahora, sabemos que el número de términos que sumamos es \(256 = 6 \cdot 42 + 4 = 6 \cdot 43 -2\). sumamos entonces los primeros seis (calculados a mano), multiplicamos por 43, restamos los dos últimos y listo. A mi me dio cinco.

EDIT: solver.EXE(quiel) no aparece, así que dejo un croquis de la demostración "estándar":

hay que calcular todos los términos hasta el octavo a mano, que no es tan grave. Entonces uno ve que los términos \(a_6\) y \(a_7\) son iguales a los términos \(a_0\) y \(a_1\). Partiendo de ese caso base, uno demuestra que vale que \(a_{n+6} = a_{n}\) por inducción, usando la fórmula recursiva. Para calcular la suma, hay una explicación breve en la resolución..

Si se necesitan más detalles, los agrego hoy o mañana a más tardar. Saludos y buena suerte.

#3 hookdump

si no es mucha molestia alguien podria dar unos detallecitos mas sobre la demostracion estandar? 🙂

Firma
$$\displaystyle\lim_{dom \to lun} = paja$$

http://hookdump.com

#4 Yossarian

supongo que es un poco tarde, pero acá va:
Demostremos por inducción que vale\(P(n): a_n = a_{n+6}\).

Hacemos a mano los primeros dos casos.

Para el siguiente, hacemos inducción global [chicos, SIEMPRE SE HACE INDUCCIÓN GLOBAL]:

supongamos que vale \(P(k)\) para todo \(k<n\). Queremos ver que entonces vale\(P(n)\)

\(a_n = a_{n-1} + a_{n-2} = (HI) a_{(n-1)+6 = n+5} - a_{(n-2)+6 = n+4} = a_{n+6} .\) QED

Saludos.

#5 Frangipani

Yo la sumatoria la resolvi de este modo. No se si está bien explicada la idea:

$$\sum_{k=0}^{255}{a_{k}}$$

yo se que tengo 256 términos, los términos son de la pinta:

$$a_{0}=1,\qquad a_{1}=3,\qquad a_{2}=2,\qquad a_{3}=-1,\qquad a_{4}=-3,\qquad a_{5}=-2$$

Y luego comienzan a repetirse tal que:

$$a_{n+6}=a_{n}$$
entonces en módulo 6 si (no se escribir congruencia con Latex 😛) n=0 \(a_{n}=a_{0}\) n=1 \(a_{n}=a_{1}\) n=2 \(a_{n}=a_{2}\) n=3 \(a_{n}=a_{3}\) n=4 \(a_{n}=a_{4}\) n=5 \(a_{n}=a_{5}\)

Yo quiero sumar desde \(a_{0}\) hasta \(a_{255}\)

Primero tengo en cuenta que si sumo desde \(a_{0}\) hasta \(a_{5}\) me queda cero.
Entonces cada vez que sume desde \(a_{0}\) hasta un \(a_{n}\) talque n sea congruente a 5 módulo 6, la suma será igual a 0.

\(255 = 6.42+3\) es decir que si sumaba hasta \(251 =6.42-1\)me iba a quedar 0, y de ahí sumaba \(a_{0}+a_{1}+a_{2}+a_{3}=1+2+3-1=5\)

Firma

"Locura es hacer siempe lo mismo y esperar diferentes resultados" Albert Einstein
"Most People are other people. Their thoughts are someone elses opinions, their lives a mimicry, their passions a quotation" Oscar Wilde

#6 Quimey

\equiv = \(\equiv\)

Firma

Quimey

#7 Frangipani

Quimey escribió:

\equiv = \(\equiv\)

Buenísimo!!!! gracias! 🙂