In general recurrence relations do not have a closed form. However, Fib does. 

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

Lets guess that f(n) = a^n  for some a (usually denoted alpha)
Plug the guess into the recurrence relation

   a^n = a^(n-1) + a^(n-2)

factor out a^(n-2)

   a^2 - a^1 - 1 = 0

Solve for a
  a = [1 (+-) sqrt( (-1)^2 - 4 * 1 * (-1))] / (2 * 1)
    = (1 (+-) sqrt(5))/2

Therefore 
  f'(n)  = [ (1 + sqrt(5))/2 ]^n   and 
  f''(n) = [ (1 - sqrt(5))/2 ]^n   
both satisfy f(n) = f(n-1) + f(n-2)

Note that if both f' and f'' both satisfy f(n) = f(n-1) + f(n-2)
it follows that any linear combination does as well.
  Let f(n) = c*f'(n) + d*f''(n)

Now we must satisfy f(0)=0,  f(1)=1

  f(0) = c*(a')^0 + d*(a'')^0 = c+d = 0
       ie d= -c
  f(1) = c*(a')^1 + d*(a'')^1 = c(1 + sqrt(5))/2 - c(1 - sqrt(5))/2 =  1
simplify               c*sqrt(5) = 1
                       c = 1/sqrt(5)

Hence 
  f(n)  = 1/sqrt(5) [ [(1+sqrt(5))/2]^n - [(1-sqrt(5))/2]^n ]

===========================================================

The timing is complexity for fib

Recurrence relations
  T(0) = T(1) = 1
  T(n) = 1 + T(n-1) + T(n)

Let TT(n) = T(n) + 1  

Put T(n) = TT(n)-1  into the recurrence relations
  TT(0)-1 = TT(1)-1 = 1
  TT(n)-1 = 1 + TT(n-1)-1 + TT(n-2)-1  

Simplify
  TT(0) = TT(1) = 2
  TT(n) = TT(n-1) + TT(n-2)

Solve this as done above.