We use the dyadic representations of $\sqrt{2008}$ and $\sqrt{2009}$:
$$\sqrt{2008} = \overline{01}1100.\overline{a_1}a_2\cdots\overline{(2)}, \quad \sqrt{2009} = \overline{01}1100.b_1b_2\cdots\overline{(2)}.$$
First, we prove that there are infinitely many even numbers by contradiction. Suppose that there are only finitely many even numbers in the sequence. Then there exists a positive integer $N$, and for every positive integer $n > N$, $f_n$ must be odd. We consider $n_1 = N+1$, $n_2 = N+2$, .... We observe that in dyadic representation
$$f_{n_i} = \overline{101100b_1b_2\cdots b_{n_i}}_{(2)} + \overline{101100a_1a_2\cdots a_{n_i}}_{(2)}$$
This number is equal to $b_{n_i} + a_{n_i}$ modulo 2. As $f_{n_i}$ is odd, we have $\{b_{n_i}, a_{n_i}\} = \{0, 1\}$. Hence,
$$\sqrt{2008} + \sqrt{2009} = \overline{1011001.c_1c_2\cdots c_{N-1}111\cdots}_{(2)}$$
Therefore, $\sqrt{2008} + \sqrt{2009}$ must be rational, which is impossible, as we know that it is irrational. Hence, our hypothesis must be wrong, which proves the existence of infinitely many even numbers in the sequence.

In a similar way we can prove the existence of infinitely many odd numbers in the sequence. Let
$$g_n = [2^n \sqrt{2009}] - [2^n \sqrt{2008}],$$
apparently $g_n$ and $f_n$ have the same parity. Hence, for $n > N$, $g_n$ is even. We observe also that in dyadic representation
$$g_{n_i} = \overline{101100b_1b_2\cdots b_{n_i}}_{(2)} - \overline{101100a_1a_2\cdots a_{n_i}}_{(2)}$$
This number is equal to $b_{n_i} - a_{n_i}$ modulo 2. As $g_{n_i}$ is odd, we have $b_{n_i} = a_{n_i}$. Thus,
$$\sqrt{2009} - \sqrt{2008} = \overline{0.d_1d_2\cdots d_{N-1}000\cdots}_{(2)}$$
and this would imply the rationality of $\sqrt{2009} - \sqrt{2008}$, which is impossible. Hence, there are infinitely many odd numbers in the sequence.