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.

I recently came across a post on SO, asking to calculate the least two decimal digits of the integer part of $(4+\sqrt{11})^{n}$, for any integer $n \geq 2$ (see here).

The author presented a Java implementation using a BigInteger class and so forth, but the answer (given by someone else) was much simpler:

$$\forall n \geq 2 : \lfloor(4+\sqrt{11})^{n}\rfloor \pmod{ 100}=\lfloor(4+\sqrt{11})^{n+20}\rfloor \pmod {100}.$$

So in essence, we only need to calculate $(4+\sqrt{11})^{n}$ for every $n$ between $2$ and $21$.

I have unsuccessfully attempted to find a counterexample, using a BigRational class and a fast-converging $n$th-root algorithm for calculating $\sqrt[n]{A}$.

My question is then, how can we prove or refute the conjecture above?

Pardon my tags on this question, wasn't sure what else to put besides irrational-numbers.

share|improve this question

migrated from mathoverflow.net Feb 23 at 22:51

This question came from our site for professional mathematicians.

1  
Could you perhaps link to the SO post? –  quid Feb 23 at 15:45
2  
This is probably more appropriate for m.SE, but it is an interesting question! –  Noah Snyder Feb 23 at 15:58
    
@quid, done; thanks. –  barak manos Feb 23 at 16:00

1 Answer 1

up vote 23 down vote accepted

Consider the linear recurrence relation $a_{n+2} = 8a_{n+1} - 5a_n$ with $a_0 = 2$ and $a_1 = 8$. It is clear that $a_n$ is an integer for all $n \geq 0$. Also, this recurrence has the following closed-form solution for all $n \geq 0$:

$a_n = (4+ \sqrt{11})^n + (4 - \sqrt{11})^n$

Since $0 < 4 - \sqrt{11} < 1$, it follows that $\lfloor(4+ \sqrt{11})^n\rfloor = a_n - 1$ for all $n \geq 0$. Periodicity of $\lfloor(4+ \sqrt{11})^n\rfloor$ follows almost immediately now: first we check that $54 = a_{2} \equiv a_{22} \text{ mod } 100$ [Edit: and $92 \equiv a_{3} \equiv a_{23} \text{ mod } 100$]. Since $a_n$ is defined via a linear recurrence, it follows that $a_n \equiv a_{n+20} \text{ mod } 100$ for all $n \geq 2$, so $\lfloor(4+ \sqrt{11})^n\rfloor \equiv \lfloor(4+ \sqrt{11})^{n+20}\rfloor \text{ mod } 100$ for all $n \geq 2$ as well.

share|improve this answer
2  
@barak -- Sure. I wanted the polynomial whose roots are $(4 + \sqrt{11})$ and $(4 - \sqrt{11})$, which turns out to be $x^2 - 8x + 5$, which corresponds to the linear recurrence I wrote. The initial conditions $a_0 = 2$ and $a_1 = 8$ were just chosen to make the answer "clean" -- they don't really matter. –  Nathaniel Johnston Feb 23 at 16:12
1  
Nice answer. Just, perhaps I am confused, but why don't you need to check also the congruence for a second value? –  quid Feb 23 at 16:15
2  
@quid -- Whoops. You're not confused. You do also have to check that $a_3 \equiv a_{23} \text{ mod } 100$ (fortunately that's true). –  Nathaniel Johnston Feb 23 at 16:17
3  
@barakmanos: It may help you to first read an explanation of why the Fibonacci numbers have the closed form $\frac{1}{\sqrt{5}} \left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^{n}\right)$. There's a general process for going getting closed forms of linear recurrences the same way, and Nathaniel just ran that process backwards starting with $(4+\sqrt{11})^n + (4-\sqrt{11})^n$. –  Noah Snyder Feb 23 at 16:18
1  
@T.J. Once you know $a_2 \equiv a_{22}$ and $a_3 \equiv a_{23}$ the recurrence tells you $a_4 = 8a_3-5a_2 \equiv 8a_{23}-5a_{22} = a_{24}$. Now just do that over and over again. –  Noah Snyder Feb 24 at 14:29

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.