Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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! – VelvetThunder Jun 30 '11 at 11:17
up vote 14 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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$.


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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.