next up previous contents
Siguiente: La conjetura de Catalan Un nivel arriba: El teorema de Goodstein Anterior: Ilustración del Teorema de

Algunos valores explícitos de la función

Calcularemos valores para argumentos de la forma $(a\cdot m^i,m)$ donde $a\in[1,m-1],\;i\in[0,m-1]\mbox{\rm y }m\geq 2.$ Definamos

\begin{eqnarray*}p(i,a,m) &=& \mathop{\rm Min}\{k\vert s_k(a\cdot m^i,m)=0\}, \\...
...mathop{\rm Min}\{k\vert s_k(a\cdot m^i,m)=(a-1)\cdot (m+k)^i\}.
\end{eqnarray*}


Entonces $q(0,a,m) = 1 \hspace{3em} p(0,a,m)=a$ Recursivamente, para $i\geq 1$, los valores de q y de p se calculan como sigue

\begin{displaymath}\begin{array}{ll}
\fbox{
\begin{minipage}[t]{15em}
\begin{ta...
...
$p(i,a,m):= s$
\end{tabbing}
\end{minipage}
}
\end{array}\end{displaymath}

Equivalentemente, se tiene las recurrencias siguientes:

\begin{displaymath}\left\{\begin{array}{rcl}
q(0,a,m) &=& 1 \\
q(i,a,m) &=& q(i-1,a,m) + p(i-1,m,m+q(i-1,a,m))
\end{array}\right.\end{displaymath}

y

\begin{displaymath}\left\{\begin{array}{rcl}
p(0,a,m) &=& a \\
\left\{\begin{...
...q(i,a,m) + p(i,a-1,m+q(i,a,m)) \end{array}
\end{array}\right.\end{displaymath}

De aquí se puede ver que q es ``constante respecto a m'', $\forall a:\;q(i,a,m)=q(i,1,m).$ Resolución del sistema de recurrencias

Proposición 4.2   Supongamos que $h_i:N\rightarrow N$ es una función tal que $\forall a,m:\;q(i,a,m)=h_i(m)-m.$ Entonces
1.
p(i,a,m)=hia(m)-m.
2.
q(i+1,a,m)=him+1(m)-m.


Demostración: Probemos 1) por inducción en a: Caso a=1:

\begin{eqnarray*}p(i,1,m) &=& q(i,1,m) \\
&=& h_i^1(m)-m
\end{eqnarray*}


Caso a+1: Sea $a\geq 1$. Supongamos que p(i,a,m)=hia(m)-m. De acuerdo a la recurrencia localizada para p tenemos

\begin{eqnarray*}p(i,a+1,m) &=& q(i,a+1,m) + p(i,a,m+q(i,a+1,m)) \\
&=& \left...
...) + \left(h_i^a(h_i(m))-h_i(m)\right) \\
&=& h_i^{a+1}(m)-m
\end{eqnarray*}


Probemos ahora 2). De la recurrencia de q obtenemos

\begin{eqnarray*}q(i+1,a,m) &=& q(i,a,m) + p(i,m,m+q(i,a,m)) \\
&=& \left(h_i...
...) + \left(h_i^m(h_i(m))-h_i(m)\right) \\
&=& h_i^{m+1}(m)-m
\end{eqnarray*}





Así pues podemos definir

\begin{eqnarray*}h_{i+1}:N &\rightarrow& N \\
m &\mapsto& h_{i+1}(m)=h_i^{m+1}(m)
\end{eqnarray*}


Ya que q(0,a,m) = 1 tenemos h0(m)=m+1. En resumen, al definir a la sucesión $\left(h_i\right)_{i\geq 0}$ haciendo

\begin{displaymath}\begin{array}{rrcl}
& h_0(m) &=& m+1 \\
\forall i\geq 1: & h_{i+1}(m) &=& h_i^{m+1}(m)
\end{array}\end{displaymath}

las funciones q y p quedan de la forma

\begin{displaymath}\begin{array}{rcl}
q(i,a,m) &=& h_i(m) -m \\
p(i,a,m) &=& h_i^a(m) -m
\end{array}\end{displaymath}




Ejemplos. Tan sólo para ilustrar los crecimientos de las funciones hi observamos:

\begin{eqnarray*}h_0(m) &=& m+1 \\
h_1(m) &=& 2m+1 \\
h_2(m) &=& 2^{m+1}(m+1) -1
\end{eqnarray*}


Para ilustrar el crecimiento de h3 vemos las primeras iteraciones de h2. Se tiene

\begin{eqnarray*}h_2^2(m) &=& {2^{1 + m + {2^{1 + m}} \left( 1 + m \right) }}
...
...m \right) }} \left( 1 + m \right) }}
\left( 1 + m \right) -1
\end{eqnarray*}


Pues bien

h3(m)=h2m+1(m).

Los crecimientos de hi con $i\geq 4$ son ciertamente inimaginables. G(a,m) con a<mm Hemos visto que si a es de la forma $a=a_i\cdot m^i$ entonces G(a,m)=p(i,ai,m). Ahora, si a<mm tenemos que $\exists a_0,\ldots,a_{m-1}\in[0,m-1]$ tales que $a=\sum_{i=0}^{m-1} a_i\cdot m_i.$ En este caso, G(a,m) es el número de veces que hay que aplicar la construcción de Goodstein para anular a todos los dígitos ai. Teniendo en cuenta que en cada iteración se incrementa la base, vemos que G(a,m) se calcula mediante el algoritmo siguiente:
\fbox{\begin{minipage}{20em}
\begin{tabbing}123\=456\=789\=012\=345\=678\=901\=2...
...e ; \\
\>$s:=s+r$\space \} ; \\
$G(a,m):= s$ 
\end{tabbing}
\end{minipage}}

next up previous contents
Siguiente: La conjetura de Catalan Un nivel arriba: El teorema de Goodstein Anterior: Ilustración del Teorema de
Guillermo Morales-Luna
2000-07-10