Exercise 4.1.19* ($\left \lfloor (1 + \sqrt{3})^{2m+1} \right \rfloor $ is divisible by $2^{m+1}$ but not by $2^{m+2}$)

Proof. Consider the sequence ${(u_n)}_{n\in \mathbb{N}}$ defined by

where ${\rho }_1=1+\sqrt{3},{\rho }_2=1-\sqrt{3}$ are the roots of the polynomial $x^2-2x-2$.

Then $u_0=u_1=2$, and

thus for all $n\in \mathbb{N}$,

therefore, by adding these two relations, we obtain

This shows that for all $n\in \mathbb{N}$, $u_n$ is an integer.

Suppose that $n=2m+1$ is odd. Since $1<\sqrt{3}<2$,

So $|1-\sqrt{3}|<1$, thus $|1-\sqrt{3}{\text{|}}^{2m+1}<1$ and ${(1-\sqrt{3})}^{2m+1}<0$, therefore

Then ${(1+\sqrt{3})}^{2m+1}-1<{(1+\sqrt{3})}^{2m+1}+{(1-\sqrt{3})}^{2m+1}<{(1+\sqrt{3})}^{2m+1}$, so

This shows that for all $m\in \mathbb{N}$,

After some experiments, we found the following pattern, which we will prove by induction:

• If $n=0$,

  $$u_0=2,u_1=2,u_3=8=2^3,u_4=20=2^2\cdot 5,$$

  so

  $${\nu }_2(u_0)=1,{\nu }_2(u_1)=1,{\nu }_2(u_3)=3,{\nu }_2(u_4)=2.$$

  This shows that $𝒫(0)$ is true.

• Suppose now that $𝒫(n)$ is true. In particular,

  $$\begin{array}{llll}\hfill u_{4n+2}& =2^{2n+3}p,& \hfill & \\ \hfill u_{4n+3}& =2^{2n+2}q,& \hfill & \end{array}$$

  where $p,q$ are odd integers. Then by (1),

  $$\begin{array}{llll}\hfill u_{4n+4}& =2(u_{4n+3}+2u_{4n+2})& \hfill & \\ \hfill & =2(2^{2n+3}p+2^{2n+2}q)& \hfill & \\ \hfill & =2^{2n+3}(2p+q)& \hfill & \\ \hfill & =2^{2n+3}r,& \hfill & \end{array}$$

  where $r=2p+q$ is odd. Therefore

  $${\nu }_2(u_{4n+4})=2n+3.$$

  Similarly,

  $$\begin{array}{llll}\hfill u_{4n+5}& =2(u_{4n+4}+u_{4n+3})& \hfill & \\ \hfill & =2(2^{2n+3}r+2^{2n+2}q)& \hfill & \\ \hfill & =2^{2n+3}(2r+q)& \hfill & \\ \hfill & =2^{2n+3}s,& \hfill & \end{array}$$

  where $s=2r+q$ is odd. Therefore

  $${\nu }_2(u_{4n+5})=2n+3.$$

  Now

  $$\begin{array}{llll}\hfill u_{4n+6}& =2(u_{4n+5}+u_{4n+4})& \hfill & \\ \hfill & =2(2^{2n+3}s+2^{2n+3}r)& \hfill & \\ \hfill & =2^{2n+4}(s+r)& \hfill & \\ \hfill & =2^{2n+4}t,& \hfill & \end{array}$$

  where $t=s+r=(2r+q)+(2p+q)=2(r+p+q)=2u$, where $u=r+p+q$ is the sum of three odd numbers, so $u$ is odd. Thus

  $$u_{4n+6}=2^{2n+5}u,$$

  where $u$ is odd. Therefore

  $${\nu }_2(u_{4n+6})=2n+5.$$

  Finally

  $$\begin{array}{llll}\hfill u_{4n+7}& =2(u_{4n+6}+u_{4n+5})& \hfill & \\ \hfill & =2(2^{2n+5}u+2^{2n+3}s)& \hfill & \\ \hfill & =2^{2m+4}(2^{2}u+s)& \hfill & \\ \hfill & =2^{2n+4}v,& \hfill & \end{array}$$

  where $v=2^{2}t+s$ is odd. Therefore

  $${\nu }_2(u_{4n+7})=2n+4.$$

  To summarize,

  $$\begin{array}{llll}\hfill {\nu }_2(u_{4n+4})& =2n+3=2(n+1)+1,& \hfill & \\ \hfill {\nu }_2(u_{4n+5})& =2n+3=(2(n+1)+1,& \hfill & \\ \hfill {\nu }_2(u_{4n+6})& =2n+5=2(n+1)+3,& \hfill & \\ \hfill {\nu }_2(u_{4n+7})& =2n+4=2(n+1)+2,& \hfill & \end{array}$$

  so $𝒫(n+1)$ is true when $𝒫(n)$ is true.

• The induction is done, so

  $$\begin{array}{llll}\hfill & \forall <!--\; FUNCTION\; APPLICATION\; -->n\in \mathbb{N},\{\begin{array}{cc}{\nu }_2(u_{4n})\hfill & =2n+1,\hfill \\ {\nu }_2(u_{4n+1})\hfill & =2n+1,\hfill \\ {\nu }_2(u_{4n+2})\hfill & =2n+3,\hfill \\ {\nu }_2(u_{4n+3})\hfill & =2n+2.\hfill \\ \hfill \end{array}& \hfill & \end{array}$$

In particular, for all integers $m\ge 0$,

In both cases,

If $m\in \mathbb{N}$, $\lfloor {(1+\sqrt{3})}^{2m+1}\rfloor$ is divisible by $2^{m+1}$ but not by $2^{m+2}$. □