求$(5+\sqrt{24})^n$的整数部分$(n\geq 1)$

未分类

---

这是一类经典的使用矩阵乘法加速的问题.
先上几个结论：
1、$(5+\sqrt{24})^n+(5-\sqrt{24})^n$是一个整数.
2、$\forall n \in[1,+\infty),(5-\sqrt{24})^n \in (0,1)$.

以上结论容易得证，此处略去，根据以上结论容易得出：

$$(5+\sqrt{24})^n+(5-\sqrt{24})^n = \lceil(5+\sqrt{24})^n\rceil$$
显然$(5+\sqrt{24})^n$是个无理数，所以$(5+\sqrt{24})^n$的整数部分就是$(5+\sqrt{24})^n+(5-\sqrt{24})^n -1$.

下面介绍求解$f_n=(5+\sqrt{24})^n+(5-\sqrt{24})^n$.
设$(5+\sqrt{24})^n=a_n+\sqrt{24}b_n$，容易得知$(5-\sqrt{24})^n=a_n-\sqrt{24}b_n$.
递推求解$a_n,b_n$:

$$\begin{align*} (5+\sqrt{24})^{n+1} &=(5+\sqrt{24})^n \times (5+\sqrt{24}) \\ &= (a_n+\sqrt{24}b_n)\times(5+\sqrt{24}) \\ &= 5a_n+24b_n+\sqrt{24}(a_n+5b_n) \end{align*}$$
也就是:$a_{n+1}=5a_n+24b_n,b_{n+1}=a_n+5b_n,a_1=b_1=1$.
构造矩阵乘法：
$$\left[ \begin{matrix} a_{n+1},b_{n+1} \end{matrix} \right] = \left[ \begin{matrix} a_n,b_n \end{matrix} \right] \times \left[ \begin{matrix} 5&,1 \\ 24&,5 \end{matrix} \right]$$
必要时使用快速幂加速矩阵乘法即可.
由上面的分析可知，$ans=2*a_n-1$.

类似的，形如$(A+\sqrt{B})^n,(A-1)^2 < B < A^2$的式子的整数部分都可以用以上介绍的方法求解.