Let a mountain of coins be an arrangement coins in rows such that the coins in each row form a single block, and that in all rows (except the bottom row) each coin touches exactly two coins from the row beneath it. How many mountains of coins have exactly k coins in the bottom row? Give a recurrence solution! ( other kinds are also accepted)
Also can anyone suggest me a nice book for recurrence?
Your "mountain" of coins is a special type of so-called "fountain" of coins. For an explicit answer to your question (spoiler alert: it involves Fibonacci numbers), see example 7 of chapter 2 in Wilf's generatingfunctionology. For a more general description of fountains of coins (where the rows aren't necessarily contiguous blocks), see his and Odlyzko's article.