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!

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

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

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