Exercise 4.4.25* ($\lfloor(1 + \sqrt{3})^{2n} \rfloor + 1$ and $\lfloor(1 + \sqrt{3})^{2n+1} \rfloor$ are divisible by $2^{n+1}$)

Proof.

(a)

Consider the sequence ${(V_n)}_{n\in \mathbb{N}}$ defined by $$\begin{array}{llll}\hfill & V_0=2,V_1=2,& \hfill & \\ \hfill & \forall <!--\; FUNCTION\; APPLICATION\; -->n\in \mathbb{N},V_{n+2}=2(V_{n+1}+V_n).& \hfill & \end{array}$$

The roots of the characteristic polynomial $p(x)=x^2-2x-2$ are

$$\alpha =1+\sqrt{3},\beta =1-\sqrt{3}.$$

By theorem 4.10,

$$V_n={(1+\sqrt{3})}^n+{(1-\sqrt{3})}^n={\alpha }^n+{\beta }^n.$$

We note that $-1<1-\sqrt{3}<0$, thus $0<{(1-\sqrt{3})}^{2n}<1$ and $-1<{(1-\sqrt{3})}^{2n+1}<0$. Therefore

$$\begin{array}{llll}\hfill {(1+\sqrt{3})}^{2n}& <{(1+\sqrt{3})}^{2n}+{(1-\sqrt{3})}^{2n}<{(1+\sqrt{3})}^{2n}+1,& \hfill & \\ \hfill {(1+\sqrt{3})}^{2n+1}-1& <{(1+\sqrt{3})}^{2n+1}+{(1-\sqrt{3})}^{2n+1}<{(1+\sqrt{3})}^{2n+1},& \hfill & \end{array}$$

so

$$\begin{array}{llll}\hfill & V_{2n}-1<{(1+\sqrt{3})}^{2n}<V_{2n},& \hfill & \\ \hfill & V_{2n+1}<{(1+\sqrt{3})}^{2n+1}<V_{2n+1}+1.& \hfill & \end{array}$$

This shows that

$$\begin{array}{llll}\hfill \lfloor {(1+\sqrt{3})}^{2n}\rfloor +1& =V_{2n},& \hfill & \\ \hfill \lfloor {(1+\sqrt{3})}^{2n+1}\rfloor & =V_{2n+1}.& \hfill & \end{array}$$

It remains to show by induction that $2^{n+1}\mid V_{2n}$ and $2^{n+1}\mid V_{2n+1}$. Consider the proposition

$$𝒫(n):2^{n+1}\mid V_{2n}\text{ and }{2}^{n+1}\mid V_{2n+1}.$$

• First $2\mid V_0=2$ and $2\mid V_1=2$, so $𝒫(0)$ is true.

• Suppose now that $𝒫(n)$ is true for some integer $n\ge 0$. Then $2^{n+1}\mid V_{2n}$ and $2^{n+1}\mid V_{2n+1}$. Therefore

  $$2^{n+2}\mid V_{2n+2}=2(V_{2n+1}+V_{2n}),$$

  and

  $$2^{n+2}\mid V_{2n+3}=2(V_{2n+2}+V_{2n+1}).$$

  Then $𝒫(n+1)$ is true, and the induction is done.

• In conclusion,

  $$\forall <!--\; FUNCTION\; APPLICATION\; -->n\in \mathbb{N},\{\begin{array}{cc}{2}^{n+1}\mid V_{2n}\hfill & =\lfloor {(1+\sqrt{3})}^{2n}\rfloor +1\hfill \\ 2^{n+1}\mid V_{2n+1}\hfill & =\lfloor {(1+\sqrt{3})}^{2n+1}\rfloor .\hfill \end{array}$$

(b)

As counterexamples, $2^3\mid V_2=V_{2\cdot 1}=8$, and $2^5\mid V_6=V_{2\cdot 3}=416=32\cdot 13$, so for some values of the indices $2n$, $V_{2n}$ is divisible by a higher power of $2$ than $2^{n+1}$(perhaps it is the answer waited by NZM, but we can prove a little more).

After some experiment (see the note below), we conjecture that

$$\{\begin{array}{cc}{\nu }_2(V_{2n})\hfill & =n+1+\chi (n),\hfill \\ {\nu }_2(V_{2n+1})\hfill & =n+1,\hfill \end{array}$$

where

$$\chi (n)=\{\begin{array}{cc}1\hfill & \text{if }n\text{ is odd},\hfill \\ 0\hfill & \text{if }n\text{ is even}.\hfill \end{array}$$

(We cannot prove this property by induction.)

Since $2^{n+1}\mid V_{2n}$ and $2^{n+1}\mid V_{2n+1}$ by part (a), we can consider the two sequences ${(S_n)}_{n\in \mathbb{N}},{(T_n)}_{n\in \mathbb{N}}$ with integer values, defined by

$$S_n=\frac{V_{2n}}{2^{n+1}},T_n=\frac{V_{2n+1}}{2^{n+1}}.$$

Since $V_{2n+2}=2V_{2n+1}+2V_{2n}$ and

$$V_{2n+3}=2V_{2n+2}+2V_{2n+1}=2(2V_{2n+1}+2V_{2n})+2V_{2n+1}=6V_{2n+1}+4V_{2n},$$

we obtain

$$\begin{array}{llll}\hfill \frac{V_{2n+2}}{2^{n+2}}& =\frac{V_{2n+1}}{2^{n+1}}+\frac{V_{2n}}{2^{n+1}},& \hfill & \\ \hfill \frac{V_{2n+3}}{2^{n+2}}& =3\frac{V_{2n+1}}{2^{n+1}}+2\frac{V_{2n}}{2^{n+1}},& \hfill & \end{array}$$

that is

$$\begin{array}{llll}\hfill & \begin{array}{cc}{S}_{n+1}\hfill & =S_n+T_n\hfill \\ T_{n+1}\hfill & =2S_n+3T_n,\hfill \end{array}& \hfill & \end{array}$$

so

$$\begin{array}{lll}\hfill & \left(\begin{array}{c}\hfill S_{n+1}\hfill \\ \hfill T_{n+1}\hfill \end{array}\right)=\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 3\hfill \end{array}\right)\left(\begin{array}{c}\hfill S_n\hfill \\ \hfill T_n\hfill \end{array}\right),\left(\begin{array}{c}\hfill S_0\hfill \\ \hfill T_0\hfill \end{array}\right)=\left(\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right).& \hfill \text{(1)}\end{array}$$

The characteristic polynomial of $A=\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 3\hfill \end{array}\right)$ is

$$p_A(x)=\left|\begin{array}{cc}\hfill 1-x\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 3-x\hfill \end{array}\right|=x^2-4x+1={(x-2)}^2-3,$$

By (1), for all $n\in \mathbb{N}$,

$$\begin{array}{lll}\hfill \left(\begin{array}{c}\hfill S_n\hfill \\ \hfill T_n\hfill \end{array}\right)=A^n\left(\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right).& & \hfill \text{(2)}\end{array}$$

The Cayley-Hamilton Theorem gives $A^2=4A-I$, thus $A^{n+2}=4A^{n+1}-A^n$, and (2) shows that for all $n\in \mathbb{N}$,

$$\begin{array}{lll}\hfill S_{n+2}=4S_{n+1}-S_n,S_0=1,S_1=2,& & \hfill \\ \hfill T_{n+2}=4T_{n+1}-T_n,T_0=1,T_1=5.& & \hfill \end{array}$$

Since $T_{n+2}\equiv T_n(\mathit{mod}2)$ for all $n$, where $T_0\equiv T_1\equiv 1(\mathit{mod}2)$, then $T_n\equiv 1(\mathit{mod}2)$, thus $T_n$ is odd for every index $n$, and $V_{2n+1}=2^{n+1}{T}_n$. This proves that

$${\nu }_2(V_{2n+1})=n+1.$$

Moreover $S_{n+2}\equiv -S_n(\mathit{mod}4)$, and $S_0\equiv 1,S_1\equiv 2(\mathit{mod}4)$, thus $S_{2n}\equiv {(-1)}^n(\mathit{mod}4)$ and $S_{2n+1}\equiv 2{(-1)}^n(\mathit{mod}4)$, so $S_{2n}=4k+{(-1)}^n$, where $k$ is an integer, is odd and $S_{2n+1}=4k+2{(-1)}^n=2(2k+{(-1)}^n)$ is twice an odd integer.

Since $V_{2n}=S_n{2}^{n+1}$, ${\nu }_2(V_{2n})=n+1$ if $n$ is even, and ${\nu }_2(V_{2n})=n+2$ if $n$ is odd.

In conclusion,

$$\{\begin{array}{cc}{\nu }_2(V_{2n})\hfill & =n+1+\chi (n),\hfill \\ {\nu }_2(V_{2n+1})\hfill & =n+1,\hfill \end{array}$$

where

$$\chi (n)=\{\begin{array}{cc}1\hfill & \text{if }n\text{ is odd},\hfill \\ 0\hfill & \text{if }n\text{ is even}.\hfill \end{array}$$