Using induction to prove $3$ divides $\left \lfloor\left(\frac {7+\sqrt {37}}{2}\right)^n \right\rfloor$ How can I use induction to prove that $$\left \lfloor\left(\cfrac {7+\sqrt {37}}{2}\right)^n \right\rfloor$$ is divisible by $3$ for every natural number $n$?
 A: Since
$$
\left(x-\frac{7+\sqrt{37}}2\right)\left(x-\frac{7-\sqrt{37}}2\right)=\left(x-\frac72\right)^2-\frac{37}4=x^2-7x+3\;,
$$
the recurrence relation
$$x_n=7x_{n-1}-3x_{n-2}$$
has solutions
$$
x_n=c_1\left(\frac{7+\sqrt{37}}2\right)^n+c_2\left(\frac{7-\sqrt{37}}2\right)^n\;.
$$
With $c_1=c_2=1$ we have $x_0=2$ and $x_1=7$. Since $0\lt\frac{7-\sqrt{37}}2\lt1$ and $x_n$ is an integer,
$$
\left\lfloor\left(\frac{7+\sqrt{37}}2\right)^n\right\rfloor=x_n-1\;.
$$
Now you just need to use the recurrence relation to show that the property that $x_1$ has remainder $1$ mod $3$ is inherited by the remaining terms.
A: Consider the recurrence given by
$$x_{n+1} = 7x_n - 3 x_{n-1}$$ where $x_0 = 2$, $x_1  = 7$.
Note that $$x_{n+1} \equiv (7x_n - 3 x_{n-1}) \pmod{3} \equiv (x_n + 3(2x_n - x_{n-1})) \pmod{3} \equiv x_n \pmod{3}$$
Since $x_1 \equiv 1 \pmod{3}$, we have that $x_n \equiv 1 \pmod{n}$. Ths solution to this recurrence is given by
$$x_n = \left( \dfrac{7+\sqrt{37}}{2} \right)^n + \left( \dfrac{7-\sqrt{37}}{2}\right)^n \equiv 1 \pmod{3}$$
Further, $0 < \dfrac{7-\sqrt{37}}{2} < 1$. This means $$3M < \left( \dfrac{7+\sqrt{37}}{2} \right)^n < 3M+1$$ where $M \in \mathbb{Z}$. Hence, we have that
$$3 \text{ divides }\left \lfloor \left (\dfrac{7+\sqrt{37}}{2}\right)^n \right \rfloor$$
A: Let $a=\dfrac{7+\sqrt{37}}{2}$, and $b=\dfrac{7-\sqrt{37}}{2}$.  We first show that $a^n+b^n$ is always an integer.
We have
$$a^{n+1}+b^{n+1}=(a+b)(a^n+b^n)-ab(a^{n-1}+b^{n-1})=7(a^n+b^n)-3(a^{n-1}+b^{n-1}).\tag{$1$}$$
It is easy to check that $a^0+b^0$ and $a^1+b^1$ are integers. The others are dealt with by induction using Equation $(1)$.
Note that $b\lt 1/2$, and $b$ is positive. Since $a^n+b^n$ is an integer, it follows that $\lfloor a^n\rfloor=a^n+b^n-1$. 
So we want to prove that $a^n+b^n\equiv 1\pmod{3}$. This is true for $n=0$ and $n=1$. Now from Equation $(1)$, on the assumption that $a^n+b^n \equiv 1\pmod{3}$, we obtain that $a^{n+1}+b^{n+1}\equiv 1\pmod{3}$. 
A: Hint: $$a_n = \left(\frac{7+\sqrt{37}}{2}\right)^n + \left(\frac{7-\sqrt{37}}{2}\right)^n$$
is always an integer, and there is a recurrence relation for $a_n$.  Since $0<\frac{7-\sqrt{37}}2<1$, you want to show that $a_n-1$ is divisble by $3$. Prove it by working out the recurrence relationship and use induction.
This result can be generalized. For integers $n>0$ and $d>0$:
$$\left\lfloor\left(\frac{2d+1+\sqrt{4d^2+1}}2\right)^n\right\rfloor$$
is divisible by $d$.
