i was unable to understand the second recurrence any one please help me.

http://www.algorithmist.com/index.php/UVa_10918

B represents the blank space.

Here fill up the space(starting from the top left corner) with a 2x1 domino vertically and you get

ABBBBBBBB

ABBBBBBBB

```
BBBBBBBB
```

So now you have to fill

BBBBBBBB

BBBBBBBB

BBBBBBBB

As you have already filled a 2x1 space with a domino.This is nothing but f(n-1) if you observe it.

Now if you fill the first 2 spaces of each row with a 2x1 domino horizontally,you get

AABBBBBBB

DDBBBBBBB

CCBBBBBB

So now you have to fill,

BBBBBBB

BBBBBBB

```
BBBBBB
```

This looks like what we defined for g(n) but with a reduced n.Upon counting we find that this is g(n-2).

Thus we have g(n) = f(n-1)+g(n-2).Hope you understood.