Recursiones fibonacci

DEFINICIONES RECURSIVAS
EJEMPLO 1 forma explícita forma recursiva n!  1 2 3 . . . n forma explícita n!  n n 1 ! fn n fn 1 fn  n fn 1 forma recursiva, operacionales forma recursiva, funcionales,f n  n! forma recursiva, sucesión

0! 1! 2! 3!

   

1 1 2 3

0! 1! 2!

EJEMPLO 2 fn  n fn 1 0! 1! 2! 3!     1 1 2 3

0!  1

0! 1! 2! 0!  6

fn  n fn 1 f0 6 f1 1 66 f 2 2 6  12 ...

EJEMPLO 3 Sucesión de Fibonacci fn  fn 1  fn 2

f0 f1 1

f 2  f 1 f 0  11  2 f 3  f 2 f 1  21  3 ... f 50  MÉTODO PARA RESOLVER ECUACIONES EN DIFERENCIAS fn  fn1  fn 2 POSIBLES FORMAS DE LA SOLUCIÓN 1

f n  An  B f n  An 2  Bn  C válida para casi todas las ecuaciones f n  Ar n

1. Sustituir la solución en la ecuación fn  fn 1  fn 2 Ar n  Ar n1  Ar n 2 2. Despejar A, despejar r para obligar a que se cumpla la igualdad despejar A: Ar n A r n 1  r n 2 A puede ser cualquier número rn  rn 1  rn 2 despejar r: rn  rn 1  rn 2 r n r n r 1 r 2 1  r 1r 2 1  r 1  r 2 r2 r2  r  1 r 1  1 5  1  1. 618 033 988 749 89 2 2 1 r2 1 5  0. 618 033 988 749 895 2 2 3. Plantear la solución (las soluciones) f1 n  A1 f2 n  A2 f general n A 1
5 1 2 5 1 2 n n 5 1 2 n 5 1 2 n

 A2

4. Encontrar el valor de las constantes utilizando los valores iniciales f0 f1 1 f 0  A1 f 1  A1
5 1 2 5 1 2 0 1

 A2  A2

5 1 2 51 2

0 1

1 1

A1  A2  1 A1 A1 
5 1 2 1 10

 A2 5 
1 2

5 1 2

1
1 2 1 10

, A2 

5

5. Plantear la solución final fn 
1 10

5 

1 2

5 1 2

n



1 21 10

5

5 1 2

n

(forma explícita de la serie de Fibonacci)

2

EL RESULTADO DE LA FUNCIÓN TIENE QUE SER UN VALOR ENTERO f0  f1  f2  f3  f4  ... f 48  f 49  f 50 
1 10 1 101 10 1 10 1 10 1 10 1 10 1 10

5  5  5  5  5  5  5  5 

1 2 1 2 1 2 1 2 1 2

5 1 2 5 1 2 5 1 2 5 1 2 5 1 2

0 1 2 3 4

    
48 49 50

1 2 1 2 1 2 1 2 1 2

1 10 1 10...