###### tags: `數學問題`
$\begin{align}\end{align}$
# 遞迴、猴子分桃問題

### 猴子分桃問題
[原文網址](https://kknews.cc/education/n5joeg8.html)

花果山上五猴，一日採摘桃子若干。因天色已晚，相約明日再分。一猴夜不能寐，起來先嘗一桃，再自行將桃分為5份，恰巧均分，並無餘數，取走1份。其後又有一猴夜不能寐，也來先嘗一桃，然後將桃分為5份，取走1份，也無餘數。五猴均如是行之。次日清晨，5猴醒來，見桃子仍是一堆，且正好均分，歡天喜地。問五猴至少採摘桃子多少才能如此進行？

[解1]:

設五猴采桃總數為 $a_0$，第 $n$ 猴取後剩餘的桃子數為 $a_n$，依題意，有：
$\begin{align}a_{n+1}=(a_n-1)\cdot\frac{4}{5}\end{align}$
$\begin{align}a_{n+1}+4=(a_n+4)\cdot\frac{4}{5}\end{align}$

因此 $<a_n+4>$ 是一個公比為 $\frac{4}{5}$ 的等比數列，因此
$\begin{align}a_n+4=(a_0+4)\cdot(\frac{4}{5})^n\end{align}$

五猴夜裡的自行分配能夠順利進行，
需要 $a_0+4$ 的值能將分母 $5^n$ 約掉，
所以，$a_0+4=K\cdot 5^n$
因此最少數是 $K=1$ 時，$a_0=5^5-4=3121$

[解2]:

設猴子 $A、B、C、D、E$ 分別起來吃一個並取走一份桃子，桃子的總數是 $x$，最後一隻猴子 $E$，拿走了 $a$ 個，加上它吃掉的 $1$ 個，$E$ 猴共有 $a+1$ 個桃，它看到的桃子總數是 $5a+1$；
$D$ 猴看到的是 $\begin{align}\frac{5}{4}(5a+1)+1=\frac{5^2}{4}(a+\frac{1}{5})+1=\frac{5^2}{4}(a+1-\frac{4}{5})+1=\frac{5^2}{4}(a+1)-4\end{align}$
$C$ 猴看到的是 $\begin{align}\frac{5}{4}(\frac{5}{4}(5a+1)+1)+1=\frac{5}{4}(\frac{5^2}{4}(a+1)-4)+1=\frac{5^3}{4^2}(a+1)-4
\end{align}$
$B$ 猴看到的是 $\begin{align}\frac{5}{4}(\frac{5}{4}(\frac{5}{4}(5a+1)+1)+1)+1=\frac{5^4}{4^3}(a+1)-4\end{align}$
$A$ 猴看到的是 $\begin{align}\frac{5}{4}(\frac{5}{4}(\frac{5}{4}(\frac{5}{4}(5a+1)+1)+1)+1)+1=\frac{5^5}{4^4}(a+1)-4\end{align}$
上面式子的數量必須是一個正整數，所以
$a+1$ 必須是 $4^4$ 的正整數倍，因此 $x$ 最小值為 $5^5-4=3121$

[解3]:

$A$ 猴拿走：$\begin{align}\frac{1}{5}(x-1)+1=\frac{1}{5}(x+4)\end{align}$
$B$ 猴拿走：$\begin{align}\frac{1}{5}(\frac{4}{5}(x-1)-1)+1=\frac{1}{5}(\frac{4}{5}(x+4-5)-1)+1=\frac{1}{5}(\frac{4}{5}(x+4)-5)+1=\frac{4}{5^2}(x+4)\end{align}$
$C$ 猴拿走：$\begin{align}\frac{4^2}{5^3}(x+4)\end{align}$
$D$ 猴拿走：$\begin{align}\frac{4^3}{5^4}(x+4)\end{align}$
$E$ 猴拿走：$\begin{align}\frac{4^4}{5^5}(x+4)\end{align}$
其實上面的式子就是一個公比為 $\frac{4}{5}$ 的等比數列，桃子的數量是一個正整數，因此最小值為 $x+4=5^5 \Rightarrow x=5^5-4=3121$

### 1. $a_1=2，a_2=4，a_{n+1}a_{n-1}=a_n^2+2012，n\geq 2$，求大於 $\frac{a_{2011}}{a_{2012}}+\frac{a_{2012}}{a_{2011}}$的最小整數為何？

---
[2007 AIME1 P14](https://artofproblemsolving.com/wiki/index.php/2007_AIME_I_Problems/Problem_14)
$\begin{align}a_{n+2}a_n-a_{n+1}a_{n-1}=a_{n+1}^2-a_n^2\end{align}$
$\begin{align}\frac{a_{n+2}+a_n}{a_{n+1}}=\frac{a_{n+1}+a_{n-1}}{a_n}\end{align}$
$\begin{align}\frac{a_{2013}+a_{2011}}{a_{2012}}=\frac{a_{2012}+a_{2010}}{a_{2011}}=\frac{a_3+a_1}{a_2}=\frac{1014+2}{4}=254\end{align}$
$\begin{align}\frac{a_{n+2}}{a_{n+1}}-\frac{a_{n+1}}{a_n}=\frac{a_{n-1}}{a_n}-\frac{a_n}{a_{n+1}}\end{align}$
$\begin{align}\frac{a_{2013}}{a_{2012}}-\frac{a_{2012}}{a_{2011}}=\frac{a_{2010}}{a_{2011}}-\frac{a_{2011}}{a_{2012}}=\frac{a_1}{a_2}-\frac{a_2}{a_3}=\frac{2}{4}-\frac{4}{1014}=\frac{503}{1014}\end{align}$

---

### 1. $$已知 a_{n+1}=\frac{1}{a_{n}+2}，a_{1}=2，試證明 \left<a_{n}\right>會收斂。$$

---

$$0\leqslant a_{n+2}=\frac{1}{\frac{1}{a_n+2}+2}=\frac{a_n+1}{2a_n+5}=\frac{1}{2}-\frac{1}{4a_n+10}\leqslant\frac{1}{2}$$

又因為

$$a_{n+4}-a_{n+2}=\frac{1}{4a_n+10}-\frac{1}{4a_{n+2}+10}=\frac{4(a_{n+2}-a_n)}{(4a_n+10)(4a_{n+2}+10)}$$

且

$$a_1=2，a_{2}=\frac{1}{2+2}=\frac{1}{4}，a_{3}=\frac{1}{\frac{1}{4}+2}=\frac{4}{9}，a_{4}=\frac{1}{\frac{4}{9}+2}=\frac{9}{22}，$$

所以子序列 $\left<a_{2k}\right>$ 為單調遞增，$\left<a_{2k+1}\right>$為單調遞減（從上式關係可以看出，若$a_3<a_1$，則$a_3-a_1<0$，那麼$a_5-a_3<0，a_7-a_5<0，...）$。且均有界（在$0$到$1/2$之間），因此$\left<a_{2k}\right>$，$\left<a_{2k+1}\right>$均收斂。由遞迴關係，可知它們收斂到同一個值 $L$，則

$$L=\frac{1}{L+2}$$

可求得

$$L=-1+\sqrt{2}$$

---

### 2. 已知 $\alpha，\beta$ 為方程式 $x^2-x-1=0$ 的兩根，且 $\alpha^{2013}-\beta^{2013}=m$，$\alpha^{2010}-\beta^{2010}=n$，試求 $\alpha^{2014}-\beta^{2014}$之值？答案以 $m，n$ 表示。

---

由牛頓恆等式
$x^{n+2}+y^{n+2}=(x+y)(x^{n+1}+y^{n+1})-xy(x^n+y^n)$，
$x^{n+2}-y^{n+2}=(x+y)(x^{n+1}-y^{n+1})-xy(x^n-y^n)$

或由特徵方程式逆推回二階線性遞迴
$a_{n+2}=a_{n+1}+a_n$ ，$a_n=\alpha^n-\beta^n$

$a_{2013}=a_{2012}+a_{2011}$
$a_{2012}=a_{2011}+a_{2010}$
兩式相減，$m-a_{2012}=a_{2012}-n\Rightarrow a_{2012}=\frac{1}{2}(m+n)$

所求 $a_{2014}=a_{2013}+a_{2012}=m+\frac{1}{2}(m+n)=\frac{3}{2}m+\frac{1}{2}n$

---
### 3. $a_{n+3}=a_{n+2}+a_{n+1}+a_n$

---
$x^3=x^2+x+1$
$(x-\frac{1}{3})^3-\frac{4}{3}(x-\frac{1}{3})-\frac{38}{27}=0$
令 $x-\frac{1}{3}=u+v$，$p=-\frac{4}{3}$，$q=-\frac{38}{27}$
因為$u^3+v^3=(u+v)^3-3uv(u+v)\Rightarrow (u+v)^3-3uv(u+v)-(u^3+v^3)=0$
比較係數，可知 $3uv=\frac{4}{3}$，$u^3+v^3=\frac{38}{27}\Rightarrow u^3v^3=\frac{64}{729}$，$u^3+v^3=\frac{38}{27}$
因此 $u^3$，$v^3$ 為方程式 $t^2-\frac{38}{27}t+\frac{64}{729}=0$ 的兩根，
公式解得 $t=\frac{19}{27}\pm\sqrt{(\frac{19}{27})^2-\frac{64}{729}}=\frac{19\pm\sqrt{297}}{27}$
所以 $(u_1,u_2,u_3)=\frac{\sqrt[3]{19+\sqrt{297}}}{3}(1,\omega,\omega^2)$，$(v_1,v_2,v_3)=\frac{\sqrt[3]{19-\sqrt{297}}}{3}(1,\omega,\omega^2)$
所以 $a_n=A(\frac{1}{3}+u_1+v_1)^n+B(\frac{1}{3}+u_2+v_2)^n+C(\frac{1}{3}+u_3+v_3)^n$
$a_0=-1=A+B+C$，$a_1=1=-\frac{1}{3}+$

---

### 4. $a_0=9, a_1=14, a_n=5a_{n-1}-6a_{n-2}+4n, n\geq 2$

---
[法一：生成函數]
令 $\{a_n\}\leftrightarrow f(x)$

$$\frac{f(x)-14x-9}{x^2}=5\cdot\frac{f(x)-9}{x}-6f(x)+4\left(\frac{x}{(1-x)^2}+\frac{2}{1-x}\right)$$

$\begin{align}
f(x) &=\frac{-35x^3+79x^2-49x+9}{(1-x)^2(1-2x)(1-3x)}=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{1-2x}+\frac{D}{1-3x}\\
&=\frac{5}{1-x}+\frac{2}{(1-x)^2}+\frac{1}{1-2x}+\frac{1}{1-3x}\\
&\leftrightarrow\{5+2(n+1)+2^n+3^n\}=\{3^n+2^n+2n+7\}
\end{align}$

[法二：特徵方程式]
令 $a_n=A\alpha^n+B\beta^n+Cn+D$，其中
$\alpha$，$\beta$ 為方程式 $x^2-5x+6=0$ 的根，取 $\alpha=2$，$\beta=3$，
此時 $A\cdot 2^n+B\cdot 3^n$ 的部份是符合 $A_n=5A_{n-1}-6A_{n-2}$ 的，
而 $Cn+D$ 的部份,
$Cn+D=5(C(n-1)+D)-6(C(n-2)+D)+4n$
$\Rightarrow\left\{\begin{align}C&=5C-6C+4
\\
D&=5D-5C-6D+12C\end{align}\right.\Rightarrow (C,D)=(2,7)$
再由 $a_0=9, a_1=14$
$\Rightarrow\left\{\begin{align}9 & =A+B+7\\
14 &=2A+3B+9\end{align}\right.$ 得到 $(A,B)=(1,1)$
所求 $a_n=2^n+3^n+2n+7$

### 5. 已知 $a_1，a_2，\cdots，a_n，\cdots$ 的每一項均為正整數，且此數列為遞增數列，即（$a_1\leq a_2\leq \cdots \leq a_n\leq a_{n+1}\leq\cdots$），已知 $a_{n+2}=3a_{n+1}-a_n$，其中 $n$ 為正整數，若 $a_6=280$，則 $a_1+a_2+a_3+a_4+a_5=？$

---

答：$176$
$a_6=55a_2-21a_1=280$
找到一組整數解 $(a_1,a_2)=(5,7)$
因為 $(55,21)=1$
所以 $a_1=5+55n$，$a_2=7+21m$
其中 $m，n$ 為正整數
然後代回遞迴得 $a_1$～$a_5$ 分別是：$5，7，16，41，107$