Domino tiling of a 2xN rectangle in O(ln n)
In your second attempt you tried to fixate the $(k+1)$th term. But instead of the two cases

1 2 ... k k+1 k+2 ... n
           | 
           |


and 

1 2 ... k k+1 k+2 ... n
           ----- 
           -----


there exist a third case:

1 2 ... k k+1 k+2 ... n
        ---- 
        ----


So if $n = 2 k$, then you have $f(k)f(k-1)$ for the first case, $f(k)f(k-2)$ for the second one, and $f(k-1)f(k-1)$ for the third one. This gives in total:

$f(2k) = f(k)f(k-1) + f(k)f(k-2) + f(k-1)f(k-1) = f(k)[f(k-1) + f(k-2)] + f(k-1)f(k-1) = f(k)^2 + f(k-1)^2$. 

Now this formula looks like the formula for $F(2n+1)$ that you posted. 


  Because the Fibonacci Numbers can be generated in O(lgn) using
  
  F(2n)=F(n)F(n+1)+F(n−1)F(n)
  
  F(2n+1)=F(n)F(n)+F(n−1)F(n−1)


Simple reason: the formula assumes that $F(1) = F(2) = 1$ while you have $f(0) = f(1) = 1$. So after an index shift it should match. 

Identical procedure for the odd case $n = 2k + 1$. 



edit: Tried to do the index shift but failed. Reason was, that you wrote down the wrong formula for $F(2n+1)$. It should be $F(2n+1)=F(n)^2+F(n+1)^2$. Then the index shift works: 

$f(2k) = F(2k+1) = F(k)^2+F(k+1)^2 = f(k-1)^2 + f(k)^2$.