|
=Relaciones de Recurrencia=
<math>
\documentclass{letter}
\usepackage{amsmath,amssymb}
La explicación de relaciones de recurrencia se encuentra como archivo [http://200.75.54.234/~andresbotero/relacionesderecurrencia.pdf en este enlace] y puede ser descargado como archivo fuente de TeXmacs [http://200.75.54.234/~andresbotero/relacionesderecurrencia.tm en este enlace]. Si quiere ayudarnos a construir la versión Wiki del documento bienvenido.
%%%%%%%%%% Start TeXmacs macros
\catcode`\à=\active \defà{\`a} \catcode`\À=\active \defÀ{\`A}
\catcode`\á=\active \defá{\'a} \catcode`\Á=\active \defÁ{\'A}
\catcode`\ä=\active \defä{\"a} \catcode`\Ä=\active \defÄ{\"A}
\catcode`\â=\active \defâ{\^a} \catcode`\Â=\active \defÂ{\^A}
\catcode`\å=\active \defå{{\aa}} \catcode`\Å=\active \defÅ{{\AA}}
\catcode`\ç=\active \defç{\c{c}} \catcode`\Ç=\active \defÇ{\c{C}}
\catcode`\è=\active \defè{\`e} \catcode`\È=\active \defÈ{\`E}
\catcode`\é=\active \defé{\'e} \catcode`\É=\active \defÉ{\'E}
\catcode`\ë=\active \defë{\"e} \catcode`\Ë=\active \defË{\"E}
\catcode`\ê=\active \defê{\^e} \catcode`\Ê=\active \defÊ{\^E}
\catcode`\ì=\active \defì{\`{\i}} \catcode`\Ì=\active \defÌ{\`{\I}}
\catcode`\í=\active \defí{\'{\i}} \catcode`\Í=\active \defÍ{\'{\I}}
\catcode`\ï=\active \defï{\"{\i}} \catcode`\Ï=\active \defÏ{\"{\I}}
\catcode`\î=\active \defî{\^{\i}} \catcode`\Î=\active \defÎ{\^{\I}}
\catcode`\ò=\active \defò{\`o} \catcode`\Ò=\active \defÒ{\`O}
\catcode`\ó=\active \defó{\'o} \catcode`\Ó=\active \defÓ{\'O}
\catcode`\ö=\active \defö{\"o} \catcode`\Ö=\active \defÖ{\"O}
\catcode`\ô=\active \defô{\^o} \catcode`\Ô=\active \defÔ{\^O}
\catcode`\ù=\active \defù{\`u} \catcode`\Ù=\active \defÙ{\`U}
\catcode`\ú=\active \defú{\'u} \catcode`\Ú=\active \defÚ{\'U}
\catcode`\ü=\active \defü{\"u} \catcode`\Ü=\active \defÜ{\"U}
\catcode`\û=\active \defû{\^u} \catcode`\Û=\active \defÛ{\^U}
\catcode`\ý=\active \defý{\'y} \catcode`\Ý=\active \defÝ{\'Y}
\catcode`\ÿ=\active \defÿ{\"y} \catcode`\=\active \def{\"Y}
\catcode`\œ=\active \defœ{!`}
\catcode`\Ÿ=\active \defŸ{?`}
\catcode`\ß=\active \defß{{\ss}}
\newcommand{\tmstrong}[1]{\textbf{#1}}
\newcommand{\tmop}[1]{\operatorname{#1}}
\newcommand{\section}[1]{\medskip\bigskip
Las relaciones de recurrencia se relacionan con problemas de algoritmos recurrentes, demostraciones por inducción y definiciones iterativas, ya que es posible transformar definiciones recursivas en definiciones iterativas, o bien expresar una relación de recurrencia como un algoritmo recursivo y en el caso de la inducción, esta también apela a un caso por defecto y se invoca a un caso previo (la hipótesis de inducción) para llegar a una demostración general.
\noindent\textbf{\LARGE #1}\vspace{-3ex}
\noindent}
%%%%%%%%%% End TeXmacs macros
==Torres de Hanoi==
\begin{document}
Las torres de Hanoi son un viejo problema para ampliar más la definición de este problema
\begin{center}
{\tmstrong{RELACIONES DE RECURRENCIA
{\tmstrong{Por: Andres Botero}}}}
\end{center}
\begin{flushleft}
Las relaciones de recurrencia pueden ser interpretadas en analogia a las
ecuaciones diferenciales ordinarias para caso discretos por esta razon
tambien son conocidas como ecuaciones en diferencias.
\end{flushleft}
Relaciones de recurrencia de primer orden:
Una relacion de recurrencia de primer orden esta dada de la siguiente forma:
$a_{n + 1} = \tmop{ra}_n, n \geqslant 0 y r \epsilon R$, se dice que es de
primer orden por que cada termino depende de su predecesor inmediato.
Por ejemplo:
\begin{center}
$a_{n + 1} = 3 a_n, n \geqslant 0, a_0 = 5
$
\end{center}
Los primeros tres terminos de la sucesion son los siguientes:
\begin{center}
$a_0 = 5$
\end{center}
\begin{center}
$a_1 = 3 ( a_0 ) = 3 ( 5 )$
\end{center}
\begin{center}
$a_2 = 3 ( a_1 ) = 3 ( 3 ( a_0 ) ) = 3^2 ( 5 )$
\end{center}
Lo que nos lleva rapidamente a la solución general de la relación de
recurrencia:
\begin{center}
\section{} $a_{n + 1} = \tmop{ra}_n$ donde n>=0, r es una contante y $a_0 =
c$
$a_n = \tmop{cr}^n$
\end{center}
Relaciones de recurrencia de segundo orden:
Sea $k \epsilon Z^+$ y $C_n, C_{n - 1}, \ldots, C_{n - 2} $numero reales
odistintos de cero, Si $a_n$ es una función discreta, entonces:
\begin{center}
$a_n C_n + a_{n - 1} C_{n - 1} + a_{n - 2} C_{n - 2} = f ( n )$
\end{center}
es una relacion de recurrencia de orden dos
Anteriormente mostramos que $a_n = \tmop{cr}^n$, si lo sustituimos en la
siguiente ecuación:
\begin{center}
$a_n C_n + a_{n - 1} C_{n - 1} + a_{n - 2} C_{n - 2} = 0$
\end{center}
tenemos:
\begin{center}
$\tmop{cr}^n C_n + \tmop{cr}^{n - 1} C_{n - 1} + \tmop{cr}^{n - 2} C_{n - 2}
= 0$
\end{center}
dividiendo por $\tmop{cr}^{n - 2} \tmop{tenemos} :$
\begin{center}
$C_n r^2 + C_{n - 1} r + C_{n - 2} = 0$
\end{center}
que llamaremos ecuacion caracteristica y las raices $r_1 $y $r_2$ son las
raices caracteristicas.
Por ejemplo :
\begin{center}
$a_n + a_{n - 1} - 6 a_{n - 2}$=0, donde $n \geqslant 0 y a_0 = 1, a_1 =
2$.
\end{center}
Donde la ecuacion caracteristica.
\begin{center}
$0 = r^2 + r - 6 = ( r + 3 ) ( r - 2 )$
\end{center}
de aca $r = 2, - 3$ y $a_n = 2^n$ y $a_n = ( - 3 )^n$ , que son soluciones
linealmente independientes.
Por eso escribimos $a_n = c_1 ( 2^n ) + c_2 ( - 3 )^n$ que es la solucion
general para la ecuación y $c_1, c_2$ son contantes arbitrarias.
Con las condiciones iniciales $a_1 = 1$ y $a_2 = 2$ podemos determinar $c_1$ y
$c_2$ de la siguiente forma:
\begin{center}
$1 = a_0 = c_1 ( 2^0 ) + c_2 ( - 3 )^0 = c_1 + c_2$
$2 = a_1 = c_1 ( 2 )^1 + c_2 ( - 3 )^1 = 2 c_1 - 3 c_2$
\end{center}
resolviendo el sistema de ecuaciones, obtenemos $c_1 = 1$, $c_2 = 0$, Por
tanto $a_n = 2^n n \geqslant 0$como una solucion ala relacion de recurrencia
dada.
\end{document}
</math>
| 