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

Question

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!

Answer 1

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.

Answer 2

$$\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$

Answer 3

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.

Answer 4

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

Answer 5

Here is an answer that uses some algebra; I don't know if it suits the OP's background, but it may help someone.

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