Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

4 Answers

up vote 7 down vote accepted

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.

share|improve this answer
2  
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.