Recursividad Relación de ejercicios

Recursividad
Relación de ejercicios
1. Demuestre por inducción que la función Q(n)=12+22+32+…+n2
puede expresarse como Q(n) = n (n+1) (2n+1) / 6
2. Demuestre por inducción que, para todo n mayoro igual que 1,
133 divide a 11n+1 + 122n-1
3. Demuestre por inducción que, para todo n mayor o igual que 4, n!>2n
4. Dado un tablero de ajedrez (de tamaño 8x8) al que le falta una casilla, ¿podemosrellenar las demás casillas utilizando únicamente teselas con forma de L?

8

8

PISTA: Realice una demostración por inducción
- ¿Cuántas casillas faltan por rellenar?
- ¿Cuántas teselas sehan colocado ya?
- ¿Cuántas casillas quedan tras colocar otra tesela?
Generalice la demostración para un tablero de tamaño 2nx2n
5. Demuestre que, con sellos de 4 y 5 céntimos, se puede franquearcualquier carta
que requiera sellos por valor de 12 o más céntimos.
6. Un granjero ha comprado una pareja de conejos para criarlos y luego venderlos.
Si la pareja de conejos produce una nueva parejacada mes y la nueva pareja
tarda un mes más en ser también productiva, ¿cuántos pares de conejos podrá
poner a la venta el granjero al cabo de un año?
FUENTE: Liber abaci, sección III

7. Dadoel siguiente fragmento de código:

static final double N = 2;
static final double PREC = 1e-6;
static double f (double x)
{
return x*x-N;
}
static double bisect (double min, double max)
{double med = (min+max)/2;
if (max-min 100)
return (x - 10);
else
return (f (f (x+11)));
}

10. Construya una función que convierta un número decimal en una cadena que represente
el valor delnúmero en hexadecimal (base 16). A continuación, generalice la función
para convertir un número decimal en un número en base B (con B n,
para encontrar su máximo común divisor
(es decir, el mayorentero positivo que divide a ambos):
- Dividir m por n para obtener el resto r (0 ≤ r < n)
- Si r = 0, el MCD es n.
- Si no, el máximo común divisor es MCD(n,r).

15. La ordenación por mezcla...