# 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$?

-
Hint: Note that $0<\alpha=\cfrac{7-\sqrt{37}}{2}<1$ - can you use this to construct a recurrence relation which has a solution of the form $\alpha^n+\beta^n$ and base your induction on that. –  Mark Bennet Oct 31 '12 at 17:36

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.

-
Was just re-reading this, and shouldn't that be $$\left\lfloor\left(\frac{7+\sqrt{37}}2\right)^n\right\rfloor=x_n-1$$? –  Thomas Andrews Jul 7 '13 at 2:17
@Thomas: Thanks -- indeed, it should; and that $x_1$ has remainder $2$ mod $3$ was even more blatantly wrong. –  joriki Jul 7 '13 at 19:22

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

-

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

-

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

-