<s>[INST] 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:


*

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

*Can anyone please show me a more natural proof?
Thanks!
 [/INST] 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.
</s>