静岡大1番解答
数学的帰納法による解法II
(1) $ a_n=4^{n+1}+5^{2n-1}=16\cdot4^{n-1}+5\cdot25^{n-1}$である．よって，
\begin{eqnarray*}
a_{n+2}&=&16\cdot4^{n+1}+5\cdot25^{n+1}\\
&=&\left(4+25 \right)\left(16\cdot4^{n}+5\cdot25^{n} \right)-4\cdot25\left(16\cdot4^{n-1}+5\cdot25^{n-1} \right)\\
&=&29a_{n+1}-100a_n
\end{eqnarray*}
となる．そして， $ a_1=21 $ ， $ a_2=4^3+5^3=(4+5)(4^2-4\dot 5+5^2)=9\cdot21 $ より， $ n=1,\ 2 $ で成立する．
$ a_n $ と $ a_{n+1} $ が21の倍数なら，上記漸化式から $ a_{n+2} $ も21の倍数である．
よって，数学的帰納法により，すべての自然数 $ n $ で成立する．
(2) $ P_n(x)=x^{n+1}+(x+1)^{2n-1} $ と置く． $ P_1(x)=x^2+x+1 $ である．
$ f(x)=x^2+x+1 $ とすると，条件(a)は満たされる．
$ f(x)=x^2+x+1 $ と推定する．
$ f(x) $ が条件(b)を満たすこと，すなわち，
すべての自然数 $ n $ に対して $ P_n(x) $ が $ f(x) $ で割り切れることを示す．
\[
P_n(x)=x^{n+1}+(x+1)^{2n-1}=4^2\cdot x^{n-1}+(x+1)\cdot(x+1)^{2(n-1)}
\]
である．よって，
\begin{eqnarray*}
P_{n+2}(x)&=&x^2\cdot x^{n+1}+(x+1)\cdot(x+1)^{2(n+1)}\\
&=&\left\{x+(x+1)^2 \right\}\left\{x^2\cdot x^{n}+(x+1)\cdot (x+1)^{2n} \right\}\\
&&\quad -x\cdot(x+1)^2\left\{x^2\cdot x^{n-1}+(x+1)\cdot (x+1)^{2(n-1)} \right\}\\
&=&(x^2+3x+1)P_{n+1}(x)-x(x+1)^2P_n(x)
\end{eqnarray*}
となる．そして， $ P_1(x)=f(x) $ ，
\[
P_2(x)=x^3+(x+1)^3=(x+x+1)\{x^2-x(x+1)+(x+1)^2\}=(2x+1)f(x)
\]
より， $ n=1,\ 2 $ で成立する．
$ P_n(x) $ と $ P_{n+1}(x) $ が $f(x) $ の倍数なら，上記漸化式から $P_{n+2}(x) $ も $ f(x) $ の倍数である．
よって，数学的帰納法により，すべての自然数 $ n $ で成立する．
直接法による解法
注意1 (2)の直接証明を二項定理で行うこともできる．
注意2 (2)を先に証明し，等式
\[
x^{n+1}+(x+1)^{2n-1}=(x^2+x+1)Q(x)
\]
に $ x=4 $ を代入すれば，
\[
4^{n+1}+4^{2n-1}=21Q(4)
\]
となる．
ここで， $ Q(x) $ が整数係数で， $ Q(4) $ が整数であることを示せば，
それから(1)が示される．