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

I am stuck on this question,

The integral parts of $(9 + 4\sqrt{5})^n$ and $(9 − 4\sqrt{5})^n$ are:

1. even and zero if $n$ is even;
2. odd and zero if $n$ is even;
3. even and one if $n$ is even;
4. odd and one if $n$ is even.

I think either the problem or the options are wrong. To me it seems that answer should be odd irrespective of $n$. Consider the following:

\begin{align*} (9 \pm 4 \sqrt{5})^4 &= 51841 \pm 23184\sqrt{5} \\ (9 \pm 4 \sqrt{5})^5 &= 930249 \pm 416020\sqrt{5} \end{align*}

Am I missing something?

-
I think you are confusing "integral part". You are interpreting it as the value of $a$ if you write $(9\pm 4\sqrt{5})^n = a+b\sqrt{n}$ with $a,b\in\mathbb{Z}$. But what they mean is the floor of $(9+4\sqrt{5})^n$, i.e., $\lfloor (9\pm 4\sqrt{5})^n\rfloor$. With that in mind, see Beni Bogosel's answer. –  Arturo Magidin Jun 29 '11 at 20:26
@Arturo Magidin:Yes,I confused on "integral part".Thanks! –  Quixotic Jun 30 '11 at 11:17

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$).

 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, one 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. Hence, since $\rm\:w'= w\:,\:$ we infer that $\rm\:w\in \mathbb Z\:$ with parity $\rm\ odd^n +\: odd^n\: =\ odd+odd\ =\ even\:.\$ Then the desired result follows easily 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\:.\:$ 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.

Here the uniqueness theorem is rather 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\:$.

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.

-
Nice point of view :) –  Beni Bogosel Jun 30 '11 at 11:44

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.

-
The recursion comes from the quadratic equation that defines $9 \pm 4 \sqrt{5}$. –  lhf Dec 23 '11 at 11:32
Dear @lhf: Yes, the minimal polynomial is $X^2-\tau\ X+\nu$, where $\tau$ is the trace and $\nu$ the norm. –  Pierre-Yves Gaillard Dec 23 '11 at 11:38