b'\n_START_ARTICLE_\nInducci\xc3\xb3n estructural y definiciones recursivas\n_START_SECTION_\nDefinici\xc3\xb3n\n_START_PARAGRAPH_\n"El conjunto \xce\xa3* de cadenas sobre el alfabeto \xce\xa3 se puede definir recursivamente por: Paso base: \xce\xbb \xe2\x88\x88 \xce\xa3*, donde \xce\xbb es la cadena vac\xc3\xada, aquella que no contiene s\xc3\xadmbolos. Paso recursivo: Si w \xe2\x88\x88 \xce\xa3* y x \xe2\x88\x88 \xce\xa3*, entonces wx \xe2\x88\x88 \xce\xa3*."\n_START_SECTION_\nTeorema de Lam\xc3\xa9\n_START_PARAGRAPH_\nEste teorema dice que siendo a y b dos n\xc3\xbameros enteros positivos con a \xe2\x89\xa5 b. Entonces, el n\xc3\xbamero de divisiones realizadas por el algoritmo de Euclides para calcular mcd(a,b) es menor o igual que cinco veces el n\xc3\xbamero de cifras decimales de b._NEWLINE_Para n>=1, dejemos que u y v sean enteros con u>v>0 de manera que el algoritmo eucl\xc3\xaddeo aplicado a u y v requiera exactamente n pasos de divisi\xc3\xb3n y de manera que u sea lo m\xc3\xa1s peque\xc3\xb1o posible satisfaciendo estas condiciones. Entonces u=F(n+2) y v=F(n+1), donde F_k es un n\xc3\xbamero de Fibonacci._NEWLINE_Adem\xc3\xa1s, el n\xc3\xbamero de pasos en el algoritmo euclidiano nunca excede 5 veces el n\xc3\xbamero de d\xc3\xadgitos del n\xc3\xbamero m\xc3\xa1s peque\xc3\xb1o. De hecho, el 5 puede reducirse a\xc3\xban m\xc3\xa1s a ln(10)/ln(phi) aproximadamente 4,785, donde phi es la proporci\xc3\xb3n de oro.\n_START_SECTION_\nConjuntos y estructuras definidas recursivamente\n_START_PARAGRAPH_\nLas definiciones recursivas de conjuntos tienen dos partes, un paso base y un paso recursivo. _NEWLINE_En el paso base se especifica una colecci\xc3\xb3n inicial de elementos. _NEWLINE_En el paso recursivo se proporcionan reglas para la formaci\xc3\xb3n de nuevos elementos del conjunto a partir de los que ya se conocen. _NEWLINE_"Regla de exclusi\xc3\xb3n: El conjunto no contiene nada m\xc3\xa1s que aquello especificado por la regla base o que se obtiene recursivamente por aplicaci\xc3\xb3n de la regla recursiva"._NEWLINE_Las definiciones recursivas pueden incluir tambi\xc3\xa9n una regla de exclusi\xc3\xb3n que especifica que un conjunto definido recursivamente no contiene m\xc3\xa1s elementos que aquellos especificados en el paso base o generados por la aplicaci\xc3\xb3n del paso recursivo.'