# Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$

Original Problem:

Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$.

I found the problem in the book Winning Solutions. I do have a solution at hand which I was able to construct duly from the given hints: At first, take $a_n=\left(\frac{7+\sqrt{37}}{2}\right)^n+\left(\frac{7-\sqrt{37}}{2}\right)^n$ and then prove that $a_{n+2}=7a_{n+1}-3a_n$ which in turn, can be used to prove that $3\ |\ a_n-1$.The proof is complete once we can prove that $a_n-1=\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$.

Questions:

1. Why would anyone think of coming up with such an ingenious recurrence? I am simply at a loss to understand the motivation behind the whole series of hints. They led me to a solution but I doubt I would have come up with it by myself.

2. Can anyone please show me a more natural proof?

Thanks!

-
There are a great many problems that have essentially the same shape. And there is a large amount of theory that connects the eigenvalues/eigenvectors of certain matrices with the solutions of linear homogeneous difference equations. –  André Nicolas Jan 4 '13 at 7:26
The first exposure most people have to this form of recurrence is the Fibonacci sequence, whose terms can similarly be written as a sum of a growing power (of the golden mean) and a shrinking power. –  mjqxxxx Jan 4 '13 at 7:28
+1 I've seen problems of similar form that were solved by looking at continued fractions. I can't remember the details unfortunately. –  user7530 Jan 4 '13 at 7:29

There are various kinds of experience you can gain that would lead you more naturally to this solution. Roughly in order, they are as follows:

The first kind is having experience with the relationship between solving linear recurrences and taking powers of a matrix by diagonalizing it. The keyword here is companion matrix; the notion of the adjacency matrix of a graph is also relevant. The canonical example here is the relationship between the Fibonacci numbers and the Lucas numbers on the one hand and taking powers of the matrix $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$ on the other, which is the adjacency matrix of a certain particularly simple graph. Slightly more generally, if $A$ is any matrix with integer coefficients, then the sequence

$$a_n = \text{tr}(A^n)$$

is a sequence of integers satisfying a linear recurrence whose coefficients are determined by the characteristic polynomial of $A$. But using linear algebra, we can be more specific: in fact $a_n$ must have the form

$$a_n = \sum_{i=1}^k \lambda_i^n$$

where $\lambda_i$ are the eigenvalues of the matrix $A$. In the Fibonacci example, $a_n$ is the Lucas numbers, and the eigenvalues are $\frac{1 \pm \sqrt{5}}{2}$; in particular, the Lucas numbers satisfy

$$L_n = \left( \frac{1 + \sqrt{5}}{2} \right)^n + \left( \frac{1 - \sqrt{5}}{2} \right)^n.$$

The second kind is having experience with some basic Galois theory and algebraic number theory. Here the key notion is understanding what a Galois conjugate of an algebraic number is, and in particular why the sum of all the Galois conjugates of an algebraic number is rational and why the sum of all the Galois conjugates of an algebraic integer is an integer. If you understand this you will immediately understand why, for example,

$$(a + \sqrt{b})^n + (a - \sqrt{b})^n$$

is always an integer. (There are more elementary ways to see this, but Galois theory / algebraic number theory is the appropriate context in which this observation should be placed.)

The third kind is having seen the notion of a Pisot-Vijarayaghavan number. These are real algebraic integers $\alpha > 1$ all of whose Galois conjugates have absolute value less than $1$. Consequently, the sequence

$$a_n = \sum_{i=1}^k \alpha_k^n$$

(where $\alpha_k$ runs over all of the Galois conjugates of $\alpha$) is dominated by $\alpha^n$, and in fact the remainder term vanishes so quickly that $a_n$ is necessarily the closest integer to $\alpha^n$.

The golden ratio $\frac{1 + \sqrt{5}}{2}$, as well as $\frac{7 + \sqrt{37}}{2}$, are both examples of Pisot-Vijarayaghavan numbers. It follows that the Lucas number $L_n$ is the closest integer to $\left( \frac{1 + \sqrt{5}}{2} \right)^n$, and if you have ever seen this result before or the corresponding result for the Fibonacci numbers then you should instantly think of using linear recurrences to solve this problem.

-
I do not have enough knowledge of linear algebra and galois theory to comment on your answer.So I hope you do not mind if I do not accept your answer right now though I seem to be convinced that the problem can attacked in more natural ways. –  user54807 Jan 5 '13 at 5:59
@Worker: it can't. I mean, you can develop the relevant material without saying all the fancy words, but the fancy words exist for a reason. –  Qiaochu Yuan Jan 5 '13 at 6:40

$$\left(7+\sqrt{37}\right)^n+\left(7-\sqrt{37}\right)^n=2(7^n+\binom n2 7^{n-2}37+\binom n47^{n-4}37^2+\cdots)$$

$$\equiv 2\{1+\binom n2+\binom n 4+\cdots\}\pmod 3$$ as $7\equiv1\pmod 3,37\equiv1\pmod 3$

$$\equiv (1+1)^n+(1-1)^n\equiv 2^n\pmod 3$$

$$\implies \left(\frac{7+\sqrt{37}}{2}\right)^n+\left(\frac{7-\sqrt{37}}{2}\right)^n\equiv1\pmod 3$$

Now, $$0<\frac{7-\sqrt{37}}{2}=\frac{12}{2(7+\sqrt{37})}<1\implies 0<\left(\frac{7-\sqrt{37}}{2}\right)^n<1$$

So, $$3k< \left(\frac{7+\sqrt{37}}{2}\right)^n<3k+1$$ for some integer $k$

-
I don't think this is an answer to the question. The OP is specifically looking for intuition as to why you would think to look at $(7 + \sqrt{37})^n + (7 - \sqrt{37})^n$ in the first place. –  Qiaochu Yuan Jan 4 '13 at 10:43
@QiaochuYuan, intuitively the sum is a rational and I wanted reach at a rational polynomial,so that I can use modulo $3$. –  lab bhattacharjee Jan 4 '13 at 10:47

Considering the number $\frac{7+\sqrt{37}}{2}$ and its quadratic conjugate $\frac{7-\sqrt{37}}{2}$: $$\left(\frac{7+\sqrt{37}}{2}\right)\left(\frac{7-\sqrt{37}}{2}\right)=\frac{49-37}{4}=3\tag{1}$$ $$\left(\frac{7+\sqrt{37}}{2}\right)+\left(\frac{7-\sqrt{37}}{2}\right)=7\tag{2}$$ Thus, we get that both of these conjugates satisfy $$x^2-7x+3=0\tag{3}$$ That is, the recurrence $$a_n=7a_{n-1}-3a_{n-2}\tag{4}$$ is satisfied by $$a_n=\left(\frac{7+\sqrt{37}}{2}\right)^n+\left(\frac{7-\sqrt{37}}{2}\right)^n\tag{5}$$ Using $(5)$, we get $a_0=2$ and $a_1=7$.

Furthermore, note that $(4)$ says that $a_n\equiv a_{n-1}\pmod{3}$ for $n\ge2$. Since $a_1\equiv1\pmod{3}$, we must have $a_n\equiv1\pmod{3}$ for $n\ge1$. That is, for $n\ge1$, $$\left(\frac{7+\sqrt{37}}{2}\right)^n+\left(\frac{7-\sqrt{37}}{2}\right)^n\equiv1\pmod{3}\tag{6}$$ Since $0<\left(\frac{7-\sqrt{37}}{2}\right)^n<1$ for $n\ge1$, we must have that $$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor\equiv0\pmod{3}\tag{7}$$

The method above is similar to many problems that deal with recursive sequences. This sort of process is often first encountered when studying the Fibonacci sequence, which satisfies the recurrence $$F_n=F_{n-1}+F_{n-2}\tag{8}$$ The recurrence $(8)$ is related to the equation $$x^2-x-1=0\tag{9}$$ since both roots of $(9)$ satify $x_i^n=x_i^{n-1}+x_i^{n-2}$, which is $(8)$ after substituting $F_n=x_i^n$. Since the recursion $(8)$ is linear, the general solution of $(8)$ is $$F_n=c_1x_1^n+c_2x_2^n$$ With enough experience with these types of equations, the answer above is pretty simple.

-

Let $\alpha = \cfrac {7+\sqrt{37}}2$ and we'll need $\beta = \cfrac {7-\sqrt{37}}2$, the conjugate of $\alpha$. We are interested in investigating $\lfloor{\alpha^n}\rfloor$.

Motivation: $\alpha^n$ is not an integer so you want to get a handle on an integer near to $\alpha^n$ and on the difference between the two.

Process: $\alpha$ is a quadratic number, and thinking about the roots of a quadratic equation [with integer coefficients], $\beta$ is clearly going to be the other root of that equation.

Note: it is important here that because $7>\sqrt {37}>6$, it is clear that $1>\beta>0$

It is no surprise then that $\alpha+\beta = 7$ and $\alpha\beta=3$ - by direct computation - so they are roots of the equation $x^2-7x+3=0$ - by introducing the conjugate, we are now working with integers, at the expense of having both $\alpha$ and $\beta$ to contend with, and a quadratic equation to handle.

Now let's investigate $a_n=\alpha^n+\beta^n$ and note that for $n>0, 0<\beta^n<1$. We have $a_0=2, a_1=7$

To get a handle on $n^{th}$ powers, multiply the quadratic through by x^{n-2} to get $$x^n-7x^{n-1}+3x^{n-2}=0$$ observe that we have $$\alpha^n-7\alpha^{n-1}+3\alpha^{n-2}=0$$ and $$\beta^n-7\beta^{n-1}+3\beta^{n-2}=0$$

And if we add those two final equations we find [note - in other circumstances we could take other linear combinations of these equations to get the same recurrence]:

$$a_n-7a_{n-1}+3a_{n-2} = 0$$

From there, the advertised solution follows through. This detail may seem laboured - I put it in to show how naturally the pieces actually fit together. Rather than seeing the solution as unmotivated and unwieldy, you should see it as a first window into some interesting and important mathematical ideas (there is more to say about linear recurrence relations/difference equations, some care to be taken in identifying conjugates - the idea of generalised integers is important too - and there are cubic cases where there are three conjugate numbers etc, and Qiaochu Yuan has indicated some other rich connections).

-
Let $\alpha = (7 + \sqrt{37})/2,$ and consider the ring $R := \mathbb Z[\alpha] = \mathbb Z[(1+\sqrt{37})/2]$. Let $x \mapsto \overline{x}$ denote the automorphism of this ring given by $\sqrt{37} \mapsto -\sqrt{37}.$ If $x \in R$ then $x + \overline{x}, x\overline{x} \in \mathbb Z$.
Note that $\alpha\overline{\alpha} = 3$, and so $(\alpha) \subset R$ is an ideal such that $R/(\alpha) = \mathbb F_3$. Furthermore, since $\alpha \equiv 0 \bmod \alpha$ (obviously), and since $\alpha + \overline{\alpha} = 7 \equiv 1 \bmod 3$, we see that the image of $\overline{\alpha}$ in $\mathbb F_3$ is $1$.
Thus the image of the integer $\alpha^n + \overline{\alpha}^n$ in $\mathbb F_3$ is equal to $0 + 1^n = 1,$ and so $$\alpha^n + \overline{\alpha}^n \equiv 1 \bmod 3.$$ (In the other answers this is checked using a recursion, or more elementary algebra.)
After this the solution is the same as in all the other answer; one has to note that $0 < \overline{\alpha}^n < 1$, so that the floor of $\alpha^n$ is $0 \bmod 3$.