Deduce that the next integer greater

Question

Deduce that the next integer greater than $(3+\sqrt 5)^n$ is divisible by $2^n$

I tried expanding it by binomial theorem but got nothing

Answer 1

There is a trick to this kind of question, which comes in handy. Note that $$0\lt 3-\sqrt 5 \lt 1$$ so so that if $$a_n=(3+\sqrt5)^n+(3-\sqrt 5)^n$$ we know that $$a_n-(3+\sqrt 5)^n=(3-\sqrt 5)^n\lt 1$$

Also $a_0=0, a_1=6$ are integers.

Now $3+\sqrt 5+3-\sqrt 5=6$ and $(3+\sqrt 5)(3-\sqrt 5)=4$ so $3+\sqrt 5$ and $3-\sqrt 5$ are roots of the equation $$x^2-6x+4=0$$

And you will find that $a_{n+1}-6a_n+4a_{n-1}=0$

From this you can deduce that $a_n$ is an integer greater than $(3+\sqrt 5)^n$ and within $1$ of it, so the next integer greater, which you wanted to find. And the recurrence will enable you to complete your induction.

---

I am using some facts about recurrences here:

If $a, b$ are roots of the equation $x^2+px+q=0$ [note that $p=-a-b, q=ab$ in this case] we have $$a^2+pa+q=0$$We multiply by $a^{n-1}$ to get $$E_a:a^{n+1}+pa^n+qa^{n-1}=0$$ and equivalently $$E_b: b^{n+1}+pb^n+qb^{n-1}=0$$ Now if we set $u_n=Aa^n+Bb^n$ we find, on taking $AE_a+BE_b$ that: $$u_{n+1}+pu_n+qu_{n-1}=0$$

Note that it is quite frequent in "nearest integer" problems with irrationals that there is some form of conjugate in the background.

Answer 2

HINT:

Let $a=3+\sqrt5, b=3-\sqrt5$

So, $a,b$ are the roots of $x^2-6x+4=0\implies t_{n+2}=6t_{n+1}-ta_n$ where $t_m=(3+\sqrt5)^m$