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

はじめに

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

問題

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

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

この数列の第2項はな〜んだ？

1の方は手計算でできると思いますが、2の方はちょっと難しいかも？ pic.twitter.com/FgdJgrQ8TV

— ａｐｕ (@apu_yokai) November 3, 2022

超略解と追加問題

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

超略解
というわけで、「1,1,3001,…」と爆発的に増加する数列でした！
フォロワーさん3000人超！みなさん一人一人のおかげでここまでくる事ができました。今後ともよろしくお願いします！
🎉㊗️🎉 pic.twitter.com/xqDVjrI92c

— ａｐｕ (@apu_yokai) November 6, 2022

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

問2.の解答

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

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

　${\displaystyle \begin{array}{rl}\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 5F_n^2+10L_n^2\cdot 5\sqrt{5}{F}_n^3+5L_n\cdot 25F_n^4+25\sqrt{5}{F}_n^5}{2^5}\end{array}}$

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

　${\displaystyle \begin{array}{rl}\frac{F_{5n}}{2}& =\frac{5L_n^4\cdot F_n+10L_n^2\cdot 5F_n^3+25F_n^5}{2^5}\\ & =\frac{5F_n((L_n^2+5F_n^2{)}^2-20F_n^4)}{2^5}\\ & =\frac{5F_n((10F_n^2+4\cdot (-1{)}^n{)}^2-20F_n^4)}{2^5}\because L_n^2=5F_n^2+4\cdot (-1{)}^n\\ & =\frac{2^4\cdot 5F_n(5F_n^4+5\cdot (-1{)}^n{F}_n^2+1)}{2^5}\end{array}}$

${\displaystyle \begin{array}{rl}\therefore F_{5n}& =5F_n(5F_n^4+5\cdot (-1{)}^n{F}_n^2+1)\end{array}}$

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

解法 $2$　割り算する

${\displaystyle \begin{array}{rl}\frac{F_{5n}}{F_n}& =\frac{{\phi }^{5n}-{\bar{\phi }}^{5n}}{{\phi }^n-{\bar{\phi }}^n}\\ & ={\phi }^{4n}+{\phi }^{3n}{\bar{\phi }}^n+{\phi }^{2n}{\bar{\phi }}^{2n}+{\phi }^n{\bar{\phi }}^{3n}+{\bar{\phi }}^{4n}\\ & =({\phi }^n-{\bar{\phi }}^n{)}^4+5{\phi }^n{\bar{\phi }}^n({\phi }^n-{\bar{\phi }}^n{)}^2+5{\phi }^{2n}{\bar{\phi }}^{2n}\\ & =25F_n^4+25\cdot (-1{)}^n{F}_n^2+5\end{array}}$

${\displaystyle \begin{array}{rl}\therefore F_{5n}& =5F_n(5F_n^4+5\cdot (-1{)}^n{F}_n^2+1)\end{array}}$

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

解法 $3$　漸化式を作る

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

${\displaystyle \begin{array}{rl}{F}_{5n}& =5F_n(5F_n^4+5\cdot (-1{)}^n{F}_n^2+1)\end{array}}$

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

${\displaystyle \begin{array}{rl}{A}_{n+1}& ={\displaystyle \frac{F_{5\cdot 5^n}}{5^{n+1}}}\\ & =\frac{5F_{5^n}(5F_{5^n}^4+5\cdot (-1{)}^{5^n}{F}_{5^n}^2+1)}{5^{n+1}}\\ & =\frac{5\cdot 5^n{A}_n(5\cdot 5^{4n}{A}_n^4-5\cdot 5^{2n}{A}_n^2+1)}{5^{n+1}}\\ & =A_n(5^{4n+1}{A}_n^4-5^{2n+1}{A}_n^2+1)\end{array}}$

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

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

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

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

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

　${\displaystyle F_{5^n}=\frac{1}{2^{5^n-1}}\sum _{k=0}^{\lfloor \frac{5^n-1}{2}\rfloor }(\genfrac{}{}{0ex}{}{5^n}{2k+1})5^k}$

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

　${\displaystyle (\genfrac{}{}{0ex}{}{5^n}{2k+1})}\equiv 0\mathrm{mod}{5}^n$

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

　${\displaystyle (\genfrac{}{}{0ex}{}{5^n}{2k+1})}{5}^k\equiv 0\mathrm{mod}{5}^n$

　となり、結局

　${\displaystyle F_{5^n}\equiv 0\mathrm{mod}{5}^n}$

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

おまけ:一般化

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

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

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

おわりに

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

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

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