How are the integral parts of $(9 + 4\sqrt{5})^n$ and $(9 − 4\sqrt{5})^n$ related to the parity of $n$?

The idea is to see that $(9+4\sqrt{5})^n+(9-4\sqrt{5})^n=2d_n$ is an even number for every $n$. This can be seen using the binomial expansion formula, and seeing that odd terms appear once with $+$ once with $-$, and even terms are always with $+$ and integers.

Moreover, $0<(9-4\sqrt{5})=9-\sqrt{80}=\frac{1}{\sqrt{81}+\sqrt{80}}<1$. This means that the integer part of the second term is zero. And for the other one, think as this

$$2d_n-1<(9+4\sqrt{5})^n<2d_n$$ so the integer part of the first term is always odd. The correct answer would be the second one (although this happens for every $n$).

[edit] As Arturo Magidin wrote in his comment, the integer part of a real number $x$, often denoted $\lfloor x \rfloor$ is the unique integer $\lfloor x \rfloor=k$ such that $k \leq x < k+1$, and it does not equal $a$ from the expansion $(9\pm 4\sqrt{5})^n=a\pm b\sqrt{5},\ a,b \in \Bbb{Z}$.

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.

To prove that $$ a_n:=\left(9+4\sqrt5\right)^n+\left(9-4\sqrt5\right)^n $$ is an even integer, it suffices to observe that $a_0=2,a_1=18$ and $$ a_{n+2}=18\ a_{n+1}-a_n $$ for $n\ge0$.

Variation.

Note that $a_n$ is an integer. Indeed $a_n$ is of the form $b_n+c_n\sqrt5$ with $b_n,c_n$ integers, and $a_n$ doesn't depend on the choice of the square root of $5$, so $c_n=0$.

Once we know that $a_n$ is an integer, we can compute it in the field $\mathbb F_2$ with two elements (in which $\sqrt5$ exists).

EDIT. The above arguments show this: If $a,b,d,n$ are integers, and if $n\ge0$, then $$ \left(a+b\sqrt d\right)^n+\left(a-b\sqrt d\right)^n $$ is an even integer.