Answer: 90

Small Hint:

Clear denominators: $a_{n+2}(1 + a_{n+1}) = a_n + 2009,$ then subtract consecutive instances

Big Hint:

Unless $a_{n+2} = a_n$ always, the differences $|a_{n+2} - a_n|$ strictly decrease forever, which is impossible; the resulting two-periodic case forces $a_1 a_2 = 2009$

Solution:

Clearing denominators, $a_{n+2}(1 + a_{n+1}) = a_n + 2009$ for all $n \ge 1.$ Subtracting each instance from the next gives $$\begin{aligned} &a_{n+2} - a_n \\ &= (a_{n+2} + 1)(a_{n+3} - a_{n+1}). \end{aligned}$$

If some difference $a_{n+2} - a_n$ were nonzero, then every later difference would be nonzero as well, and since each $a_{n+2} + 1 \ge 2,$ the identity would force $|a_3 - a_1|$ $\gt |a_4 - a_2|$ $\gt |a_5 - a_3|$ $\gt \cdots,$ an infinite strictly decreasing sequence of positive integers — impossible. Hence $a_{n+2} = a_n$ for all $n:$ the odd-indexed terms are all equal and the even-indexed terms are all equal.

The recursion then reads $a_1(1 + a_2) = a_1 + 2009,$ so $a_1 a_2 = 2009 = 7^2 \cdot 41.$ Among the factor pairs of $2009,$ the sum is smallest for $41 \cdot 49,$ giving $41 + 49 = 90.$