4
$\begingroup$

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

  • 1
    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.2012-10-31

4 Answers 4

8

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.

  • 0
    @Thomas: Thanks -- indeed, it should; and that $x_1$ has remainder $2$ mod $3$ was even more blatantly wrong.2013-07-07
6

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$

5

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

4

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