【1】について
いちいち、\alpha^{n}+\beta^{n}-3^{n} と呼ぶのも面倒なので、
\gamma_{n}=\alpha^{n}+\beta^{n}-3^{n}
と名前を付けます。
通常の帰納法(昨日法)だと
\gamma_{k} が 5 の倍数と仮定したとき、\gamma_{k+1} が 5 の倍数であることを目指す
という流れです。
\alpha^{k+1}+\beta^{k+1}=(\alpha+\beta)(\alpha^{k}+\beta^{k})-\alpha\beta(\alpha^{k-1}+\beta^{k-1}) なので、
\gamma_{k+1}=(\alpha+\beta)(\alpha^{k}+\beta^{k})-\alpha\beta(\alpha^{k-1}+\beta^{k-1})-3^{k+1}
と見ると、n=k のときの仮定だけでなく、一昨日である n=k-1 のときの仮定も必要になる「一昨日昨日法」であることが分かると思います。
一昨日昨日法になる代表的なタイプとしては
3項間漸化式 a_{n+2}=f(a_{n+1} , a_{n})
でしょう。(前2つの情報から次が決まるという構造)
ただ、神経質に「このタイプは一昨日昨日法で、このタイプは \cdots」というMr丸暗記になる必要はありません。
一昨日昨日法かどうかを最初から見抜ければいいですが、見抜けなかった場合でも上記のように途中で微調整の必要性に気づくことは可能です。
むしろ、微調整の必要性を見抜く眼力をつけることの方が、本問以外の様々な問題を解くにあたって大切です。
【2】について
今回の数列の構造について考えてみます。
例えば x_{10} は直前の x_{9} から決まるわけではなく、
x_{10}=x_{5}+1
というように、離れた x_{5} から決まります。
このことから、n=k の成立を仮定して、n=k+1 の成立を目指す通常の帰納法(昨日法)が通用しないことが分かります。
いちいちガウス記号などを下手に持ち出して、「添え字の半分」のときの成立を仮定するのも面倒です。
チマチマ仮定するのではなく、もういっそのこと「全て成立を仮定する」"人生帰納法" を選択します。
つまり、
x_{2} \leq 2\log{2}-1
x_{3} \leq 2\log{3}-1
\vdots
x_{n} \leq 2\log{n}-1
と、全て仮定し、x_{n+1} \leq 2\log{(n+1)}-1 の成立を目指します。
この帰納法のドミノ倒しの「最初のチョン」は
n=2 のときと n=3 のとき
です。
x_{2} と x_{3} は x_{1} から決まる値であり、このときは帰納法の橋がかかっていないからです。
なお、人生帰納法の代表的な使いどころは
和が絡むとき
が多いです。
例えば S_{n}=a_{1}+a_{2}+\cdots+a_{n} としたとき、a_{1} から a_{n} まで全てが決まって S_{n} が決まるからです。
まとめ
帰納法のタイプを選択する力は「問題の構造を把握する力」と直結します。
問題の構造を把握できないと、帰納法のタイプを選択できないからです。
そういった意味で、帰納法のタイプを選択するという表面的な話題だけでなく、問題自体の構造を把握しようとする態度の養成が大切だと言えましょう。
なお、この内容を書き終わったらPCが「帰納法」の変換を一発で出せなくなってしまいました。
解答はコチラ