11
$\begingroup$

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.

$\endgroup$

migrated from mathoverflow.net Feb 23 '14 at 22:51

This question came from our site for professional mathematicians.

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

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.

$\endgroup$
  • 2
    $\begingroup$ @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. $\endgroup$ – Nathaniel Johnston Feb 23 '14 at 16:12
  • 1
    $\begingroup$ Nice answer. Just, perhaps I am confused, but why don't you need to check also the congruence for a second value? $\endgroup$ – quid Feb 23 '14 at 16:15
  • 2
    $\begingroup$ @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). $\endgroup$ – Nathaniel Johnston Feb 23 '14 at 16:17
  • 3
    $\begingroup$ @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$. $\endgroup$ – Noah Snyder Feb 23 '14 at 16:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Noah Snyder Feb 24 '14 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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