######################## PROBLÈME 3: #########################

#@#  a)
F[2*n]   := F[n]^2 + F[n-1]^2;
F[2*n-1] := 2*F[n]*F[n-1] - F[n-1]^2;

F[2*n+1] := F[2*n] + F[2*n-1];
F[2*n+2] := F[2*n+1] + F[2*n];
F[n-1]   := F[n+1] - F[n];

simplify(F[2*n+1]);
simplify(F[2*n+2]);

#@#  b)

#@# récursion dyadique
F := proc(k)
  local n,a,b;
  options remember;
  
  n := ceil(k/2);
  if type(k, even) then
    F(n)^2 + F(n-1)^2;
  else
    F(n-1) * (2*F(n) - F(n-1));
  fi;
end;
F(0) := 1;
F(1) := 1;

#@# une variante plus efficace avec un seul appel récursif
#@# T(n)[1] calcule $F_n$
T := proc(n)
  local q,r,t,a,b;
  q := iquo(n, 2, 'r');
  t := T(q); a := t[1]; b := t[2];
  if (r = 1) then [a^2 + b^2, b*(2*a + b)];
             else [a*(2*b - a), a^2 + b^2];
  fi;
end;
T(0) := [0,1];
T(1) := [1,1];

#@# récursion directe, trop profonde si n est trop grand
F2 := proc(n)
  options remember;
  F2(n-1) + F2(n-2);
end;
F2(0) := 1;
F2(1) := 1;

#@# version itérative
F3 := proc(n)
  local n_1, n_2, i, t;

  n_2 := F3(0);
  n_1 := F3(1);
  for i from 2 to n do
    t := n_2 + n_1;
    n_2 := n_1;
    n_1 := t;
  od;
  t;
end;
F3(0) := 1;
F3(1) := 1;

#@# c)

FF := n-> matrix([[F[n+2],F[n+1]], [F[n+1],F[n]]]);
A := matrix([[1,1], [1,0]]);

F4 := proc(n)
  evalm(A^n)[1,1];
end;

simplify(evalm(FF(n-1)^2));

evalm(FF(n) &* A); #@# soit ${@tt FF}(n) = A^{(n+2)}$

#@# d)

simplify(evalm(FF(n-1)^3));

#@# récursion triadique (plus lent que dyadique)
F5 := proc(k)
  local n, r;
  options remember;

  r := irem(k,3);
  if r = 0 then
    n := (k-3)/3;
    F5(n+1)^3 + 3*F5(n+1)*F5(n)^2 - F5(n)^3;
  elif r = 2 then
    n := (k-2)/3;
    3*F5(n)*F5(n+1)^2 - 3*F5(n)^2*F5(n+1) + 2*F5(n)^3;
  else   # @# r = 1
    n := (k-1)/3;
    F5(n+1)^3 - 3*F5(n)*F5(n+1)^2 + 6*F5(n)^2*F5(n+1) - 3*F5(n)^3;
  fi;
end;
F5(0) := 1;
F5(1) := 1;

#@# e)
#@# précalculs: phi et a,b
z := solve(x^2 = x + 1, x);
if (evalf(z[1]) < 1) then
  phi := z[2];
else
  phi := z[1];
fi;
z := solve({a + b = 1, a * phi - b / phi = 1}, {a,b});
a := subs(z, a);

F6 := proc(n)
  local d; #@# = précision nécessaire (10 chiffres de rab)
  d := ceil(evalf(ln(a) + n * ln(phi) / ln(10))) + 10;
  round(evalf(a * phi^n, d));
end;