Cadenas de adición definiciones básicas

Solo disponible en BuenasTareas
  • Páginas : 6 (1311 palabras )
  • Descarga(s) : 0
  • Publicado : 12 de febrero de 2012
Leer documento completo
Vista previa del texto
Definiciones Básicas
Definición 1.- Sea Se={ ai } una sucesión finita de números naturales. La llamaremos cadena de adición de un número natural e si satisface:
I. 1=ao < a1 <…<ar = e,
II. ai = aj + ak para algunos j y k con 0 k j<i para toda i; 0 < i ≤ r.
Definición 2- .- Sea Se={ ai } = {1=ao < a1 <…<ar = e } una cadena de adición de un número e, el mayoríndice de la sucesión r se denomina longitud de la cadena Se y se denota por l(Se).
Definición 3.- La longitud más pequeña de todas las cadenas de adición de un número natural e se denota por l(e), esto es:
l(e) = mínimo { l(Se) Se es cadena de adición de e}.
Definición 4.- La familia de un número e (se denota por Fe), está compuesta por la unión de los elementos de las cadenas mínimas deadición del número e. Esto es:
Fe= x∈ SelSe=l(e)
Definición 5.- Considere la familia de conjuntos Gi definidos por:
Gi=i=0, G0=1 i≥1, Gi=n∈N2m-1+1≤n ≤2m
Al conjunto Gi le llamaremos Generación i-esima de números naturales.
Definición 6.- Llamamos Gip pares y nones Gin de la generación iésima a las familias definidas por:
Gip=xx=2*y;y∈ Gi-1 Gin=xx=2*y-1; y∈ Gi-1 i>1

Definición 7.- Llamamos cadenas dominante a las cadenas de adición definidas por:
Sen=ai donde ai=1 si i=0ai-1+ai-1 si 0<i≤n.
Definición 8.- Los números e de las cadenas dominantes les llamamos números dominantes.
Propiedades Importantes

Proposición 1: Sea Se = {ai} una cadena de adición tal quel(Se)>0, entonces a1=2. Esto es los primeros dos elementos de una cadena de adición tienen el valor de 1 y 2 respectivamente.
Demostración
Sea Se = {ai} una cadena de adición tal que l(Se)>0, por definición su primer elemento es a0=1 y el segundo a1= aj + ak para algunos j y k con 0 k j<1, j menores que uno y mayores o iguales a cero, solo el cero cumple por lo tanto j=0 y como k es menorigual que j y mayor o igual a cero, no tiene otra opción más que k=0. De donde a1 = aj + ak , a1 = a0 + a0 =1 + 1= 2.
Q.E.D.
Proposición 2. Sea y=e+x; x∈Fe entonces ly≤le+1
Demostración
Como x∈Fe existe Se ∙∋∙x∈ Se y lSe=l(e) sea Sy=Se∪e+x=y entonces lSy=le+1, lo que demuestra que ly≤le+1
Q.E.D.
Proposición 3: Las cadenas dominantes, son de máximo crecimiento y son únicas.
Sen=aidonde ai=1 si i=0ai-1+ai-1 si 0<i≤n
Demostración
Empezaremos por demostrar que son de máximo crecimiento. Sin pérdida de generalidad, podemos suponer que para cualquier cadena de adición de longitud finita p, que Sx=bi≠Sep=ai donde ai=1 si i=0ai-1+ai-1 si 0<i≤p, por hipótesis ambas tienen la misma longitud. Como sondiferentes entonces existe i<p y mayor que uno (ya que los dos primeros valores siempre son iguales) tal que ai≠bi, como: ai=ai-1+ai-1 y bi=bj+bk= aj+ak ya que hasta t<i bt=at con j y k que satisface: con 0 k ji-1, entonces j o k (o ambos) son menores que i-1, ya que si fueran iguales a i-1, ai=bi y como ai-1>at, para t<i-1 se cumple que ai>bi, entonces a partir de i hasta p,se cumple que at≫bt, cada vez la componente de Se p ≫Sx, lo que demuestra que es de máximo crecimiento.
Para demostrar la unicidad supongamos que existe otra cadena diferente de la dominante, ambas de longitud p, para cualquier p finito que también sea dominante esto es: Sx=e=bi≠Sep como ambas tienen longitud p, se acaba de demostrar que x < e=2p, lo que contradice que x=e, lo que contradicela hipótesis de que existe otra cadena dominante, lo que demuestra la unicidad.
Q.E.D.
Proposición 4: Los números dominantes e son de la forma e=2n.
Demostración
Como las cadenas están definidas por:
Sen=ai donde ai=1 si i=0ai-1+ai-1=2ai-1 si 0<i≤n
como a0= 1=20 y a1=2=21, tenemos para a2=2 a1=2*21=22, en general ai=2*ai-1=2* 2i-1= 2i.lo que...
tracking img