1
高校数学解説
文献あり

フォロワー3000人突破記念問題の解答と解説

66
0
$$$$

はじめに

この記事では、先日私のTwitterのフォロワー数が $3000$ 人を突破したことを記念して作った自作問題の解説をします。

問題

これがそのときの問題です。

フォロワー$3000$人突破記念問題

$1.$ (易) 一般項が次のように表される数列 $\{A_n\}$ について、 $A_2$ をもとめてください。ただし $F_k$ はフィボナッチ数列の第 $k$ 項を表し、$n$ は非負整数とします。

      $A_n:=\dfrac{F_{5^n}}{5^n}$

   $A_0=1,\qquad A_1=1,\qquad A_2=?$

$2.$ (難) 数列 $A_n$ がすべて整数となることを示してください。

$3.$ (追加問題)
   ${\displaystyle \begin{align} A_{n}\equiv 1 \mod1000 \end{align} }$  となることを示してください。

超略解と追加問題

その後で、超略解をツイートしました。

1.
   $A_2=\dfrac{F_{25}}{25}=\dfrac{75025}{25}=3001$  

2.
(超略解)
 頑張って計算することで次の漸化式が得られる。

  ${\displaystyle \begin{align} A_{n+1} &=5^{4n+1}A_n^5 -5^{2n+1}A_n^3+A_n \\ \end{align} }$

漸化式の形から明らかに $A_n$ は整数となることがわかる。

3. 
(略解)
  $n=0,1$ のとき $A_n=1$

  $n\geqq1$ のとき $A_n\equiv1\mod1000$ と仮定すると
  ${\displaystyle \begin{align} A_{n+1} &=5^{4n+1}A_n^5 -5^{2n+1}A_n^3+A_n\\ &\equiv125\cdot1^5-125\cdot1^3+1\mod1000\\ &\qquad\left(\because 5^k\equiv125\mod1000\,\,(k=3,5,7,9,\cdots)\right)\\ &\equiv1\mod1000 \\ \end{align} }$

数学的帰納法によりすべての非負整数 $n$ について成り立つ。

問2. の解答でいきなり謎の漸化式が出てきてよく分からないと思いますので、これから別解とあわせて解説していきます。

問2.の解答

解法 $1$ ド・モアブルの定理の類似を使う

ド・モアブルの定理の類似

${\displaystyle \begin{align} \left( \frac{L_n + \sqrt{5} F_n}{2} \right)^k = \frac{L_{kn} + \sqrt{5} F_{kn}}{2} \end{align} }$

 ただし $F_n$ はフィボナッチ数、 $L_n$ はリュカ数とする。

公式$1$の証明は読者への演習課題とする。

 ド・モアブルの定理の類似で $k=5$ とすると

 ${\displaystyle \begin{align} \frac{L_{5n} + \sqrt{5} F_{5n}}{2} &=\left( \frac{L_n + \sqrt{5} F_n}{2} \right)^5 \\ &= \frac{L_n^5 + 5L_n^4\cdot \sqrt{5} F_n + 10L_n^3\cdot 5 F_n^2 + 10L_n^2\cdot 5\sqrt{5} F_n ^3 + 5L_n\cdot 25 F_n^4 + 25\sqrt{5} F_n^5 }{2^5} \end{align} }$

$\sqrt{5}$ の係数を比較することで

 ${\displaystyle \begin{align} \frac{F_{5n}}{2} &= \frac{ 5L_n^4\cdot F_n + 10L_n^2\cdot 5 F_n ^3 + 25 F_n^5 }{2^5}\\ &= \frac{5F_n\left((L_n^2 + 5 F_n^2 )^2 -20 F_n^4\right) }{2^5}\\ &= \frac{5F_n\left((10 F_n^2 +4\cdot(−1)^n )^2 -20 F_n^4\right) }{2^5}\qquad\because L_n^2 = 5 F_n^2 +4\cdot(−1)^n\\ &= \frac{2^4\cdot5F_n\left(5 F_n^4 +5\cdot(−1)^nF_n^2+1 \right) }{2^5} \end{align} }$

${\displaystyle \begin{align} \therefore F_{5n} &= 5F_n\left(5 F_n^4 +5\cdot(−1)^nF_n^2+1 \right)\\ \end{align} }$

ここまでくれば、カッコ内が正整数であることと、$F_1=1$ とあわせて数学的帰納法により証明できますね。

解法 $2$ 割り算する

${\displaystyle \begin{align} \frac{F_{5n}}{F_n} &= \frac{\varphi^{5n}-\overline{\varphi}^{5n}}{\varphi^{n}-\overline{\varphi}^{n}}\\ &= \varphi^{4n}+\varphi^{3n}\overline{\varphi}^{n}+\varphi^{2n}\overline{\varphi}^{2n}+\varphi^{n}\overline{\varphi}^{3n}+\overline{\varphi}^{4n}\\ &=(\varphi^{n}-\overline{\varphi}^{n})^4+5\varphi^{n}\overline{\varphi}^{n}(\varphi^{n}-\overline{\varphi}^{n})^2+5\varphi^{2n}\overline{\varphi}^{2n}\\ &=25F_{n}^4+25\cdot(-1)^nF_n^2+5 \end{align} }$

${\displaystyle \begin{align} \therefore F_{5n} &= 5F_n\left(5 F_n^4 +5\cdot(−1)^nF_n^2+1 \right)\\ \end{align} }$

あとは解法 $1$ と同じ。

解法 $3$ 漸化式を作る

解法 $1$ 又は解法 $2$ で得られる式

${\displaystyle \begin{align} F_{5n} &= 5F_n\left(5 F_n^4 +5\cdot(−1)^nF_n^2+1 \right)\\ \end{align} }$

を使って漸化式を作ることで、より直感的な別解を作ることができます。冒頭部の「超略解」に出てきた漸化式はこれになります。

${\displaystyle \begin{align} A_{n+1}&=\dfrac{F_{5\cdot5^{n}}}{5^{n+1}}\\ &=\frac{5F_{5^n}\left(5 F_{5^n}^4 +5\cdot(−1)^{5^n}F_{5^n}^2+1 \right)}{5^{n+1}}\\ &=\frac{5\cdot5^nA_n\left(5\cdot5^{4n}A_n^4 -5\cdot5^{2n}A_n^2+1 \right)}{5^{n+1}}\\ &=A_n\left(5^{4n+1}A_n^4 -5^{2n+1}A_n^2+1 \right)\\ \end{align} }$

${\displaystyle \begin{align} \therefore A_{n+1} &=5^{4n+1}A_n^5 -5^{2n+1}A_n^3+A_n \\ \end{align} }$

漸化式の形から明らかに $A_n$ は整数となることがわかります。

解法 $4$ カタランの公式を使う

 さらなる別解として、カタランの公式を使う方法もあります。

カタランの公式

${\displaystyle F_n=\frac{1}{2^{n-1}} \sum_{k=0}^{\left\lfloor \frac{n-1}{2} \right\rfloor} {n \choose 2k+1} 5^k }$

${\displaystyle \begin{align} F_{n}&={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}\\ &={\frac {1}{2^n\sqrt {5}}}\left\{\left({1+{\sqrt {5}}}\right)^{n}-\left({1-{\sqrt {5}}}\right)^{n}\right\}\\ &={\frac {1}{2^n\sqrt {5}}}\cdot2\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} {n \choose 2k+1}\left(\sqrt{5}\right)^{2k+1}\\ &={\frac {1}{2^{n-1}}}\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} {n \choose 2k+1}5^k\\ \end{align} }$

 カタランの公式で第 $5^n$ 項を求めると

 ${\displaystyle F_{5^n}=\frac{1}{2^{{5^n}-1}} \sum_{k=0}^{\left\lfloor \frac{{5^n}-1}{2} \right\rfloor} {{5^n} \choose 2k+1} 5^k }$

 となります。
 二項係数の部分を見ると、$k=0,1$ のときは分母に$5$ を含んでいませんから

 ${\displaystyle{5^n \choose 2k+1}}\equiv0\mod5^n$

 $k>1$ のときは分母に $5$ が出てきますが、$5^k$ の方が $5$ の素因数の増加が早いので

 ${\displaystyle{5^n \choose 2k+1}}5^k\equiv0\mod5^n$

 となり、結局

 ${\displaystyle F_{5^n} \equiv0\mod5^n }$

 となります。
 したがって、数列 $A_n=\dfrac{F_{5^n}}{5^n}$ がすべて整数となることがわかりました。

おまけ:一般化

さて、更に一般化して「自然数 $k$$F_k$ を割り切ることができるようなもの」はどんな数列になるでしょうか。

OEIS:A023172 によれば、つぎのようになります。

$1, 5, 12, 24, 25, 36, 48, 60, 72, 96, 108, 120, 125, 144, 168, 180, 192, 216, 240, 288, 300, 324, 336, 360, 384, 432, 480, 504, 540, 552, 576, 600, 612, 625, 648, 660, 672, 684, 720, 768, 840, 864, 900, 960, 972, 1008, 1080, 1104, 1152, 1176, 1200, 1224, 1296, 1320,\cdots $

 この数列に出てくる $1$ より大きい数は、すべて $5$ 又は $12$ の倍数になっていることを証明できますので、証明に挑戦するのも楽しいと思います。

【お詫びと訂正】
 当初、「すべて $5$ のべき乗 又は $12$ の倍数になっていることを証明できるみたい」と書いていたのは誤りでした。($F_{5^2}$ などが反例となるため)
 お詫びして訂正いたします。

おわりに

 最後に、$A_n$ の最初の数項を具体的に書き出してみましょう。

$A_0=1$
$A_1=1$
$A_2=3001$
$A_3=475400918060101145703001$
$A_4=\underbrace{296421797648\cdots662210078001}_{128桁}$
$A_5=\underbrace{174598600118\cdots854835078001}_{650桁}$
$A_5=\underbrace{773702281896\cdots746631953001}_{3261桁}$
$\qquad\vdots$

とんでもない速さで爆発的に増加しますね!
フォロワー数 $3000$ 人突破記念問題として、とても縁起の良い数列を題材にできたと思います。

ここまでこれたのも一人一人のフォロワーさんのおかげです。
今後ともよろしくお願いします!

参考文献

[1]
中村 滋, フィボナッチ数の小宇宙, 日本評論社, 2002, p.48
投稿日:20221112
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

apu_yokai
apu_yokai
462
60443

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中