Alternative to binomial expansion, we can deduce that $\rm\:w = (9+4\sqrt{5})^n + (9-4\sqrt{5})^n\:$ is even by noting that the notion of parity uniquely extends from $\;\mathbb Z\:$ to $\:\mathbb Z[\sqrt{5}]\:$ by defining $\rm\:\sqrt{5}\:$ to be odd. Conjugating shows $\rm\:w'= w,\:$ therefore $\rm\:w\in \mathbb Z\,$ with parity $\rm\ {odd}^n + {odd}^n = odd+odd = even.\ $ The rest follows easily from $\,0<9-4\sqrt{5}<1\,$ as Beni explained. Notice, in particular, how this viewpoint is a very natural higher-degree extension of ubiquitous parity-based proofs in $\mathbb Z.$
Alternatively, it follows immediately from the fact that, mod $2$, the sequence $\rm\:w_n\:$ satisfies a monic integer-coefficient recurrence, and the first $\,2\,$ (= degree) terms are $\equiv 0.\:$ Hence by induction so are all subsequent terms, viz. $\rm\ f_{n+2} \equiv\ a\ f_{n+1} + b\ f_{n} \equiv\ 0\ $ since by induction $\rm\ f_{n+1},\ f_{n} \equiv 0.\: $ Or, said equivalently $\rm\:f_n \equiv 0\ $ by the uniqueness theorem for solutions of difference equations (recurrences). As I frequently emphasize uniqueness theorems provide very powerful tools for proving equalities.
Worth emphasis: for difference (vs. differential) equations, the uniqueness theorem is utterly trivial, amounting to the trivial induction that if two solutions of a degree $\rm\:d\:$ monic integer coefficient recurrence agree for $\rm\:d\:$ initial values then they agree at all subsequent values; equivalently, taking differences, if a solution is $\:0\:$ for $\rm\:d\:$ initial values then it is identically $\,0$. The induction step simply employs the recurrence to lift up the equality from the prior $\rm\,d\,$ values - as above for $\rm\,d=2.$
More generally the same holds true for integer-linear combinations of roots of any monic integer coefficient equation (i.e. algebraic integer roots) since they too will satisfy a monic integer coefficient recurrence, viz. the characteristic equation associated to the polynomial having said roots (the quadratic case is the widely studied Lucas sequence). Thus every term of the sequence will be divisible by $\rm\:m\:$ iff it is true for the first $\rm\:d\:$ (= degree) terms. More generally one easily checks that the gcd of all terms is simply the gcd of the initial values.
Note that, as above, one requires only the knowledge of the existence of such a recurrence. There is no need to explicitly calculate the coefficients of the recurrence; rather, only its degree is employed.