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{array}{ll} \fbox{ \begin{minipage}[t]{15em} \begin{ta... ... $p(i,a,m):= s$ \end{tabbing} \end{minipage} } \end{array}$$

Equivalentemente, se tiene las recurrencias siguientes:

$$\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.$$

y

$$\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.$$

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)=h_i^a(m)-m.

2.

q(i+1,a,m)=h_i^m+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)=h_i^a(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 h₀(m)=m+1. En resumen, al definir a la sucesión $\left(h_i\right)_{i\geq 0}$ haciendo

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

las funciones q y p quedan de la forma

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

Ejemplos. Tan sólo para ilustrar los crecimientos de las funciones h_i 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 h₃ vemos las primeras iteraciones de h₂. 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

h₃(m)=h₂^m+1(m).

Los crecimientos de h_i con $i\geq 4$ son ciertamente inimaginables. G(a,m) con a<m^m Hemos visto que si a es de la forma $a=a_i\cdot m^i$ entonces G(a,m)=p(i,a_i,m). Ahora, si a<m^m 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 aⁱ. Teniendo en cuenta que en cada iteración se incrementa la base, vemos que G(a,m) se calcula mediante el algoritmo siguiente:

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