問題はこちら（画像をクリックするとPDFファイルで開きます。）
このシリーズの一覧はこちら
数学的帰納法と背理法 第１講【互いに素であることの証明】【2002年度 東京大学】
問題はこちら（画像をクリックするとPDFファイルで開きます。） このシリーズの一覧はこちら 数学における２大証明法「数学的帰納法」と「背理法」のコラボレーション問題です。 指導者側からすると「ハイハイこれね」と言いたくなるぐらい手垢のついた問題ですが、初めて解いた時の気持ちよさは今でも覚えています。 漸化式に関する証明問題では帰納法を用いるのが常套手段です。 本問では「互いに素」であることを証明するために背理法を用いることになります。 矛盾の仕方が個人的に気持ちいいですね。 ( ...
続きを読む
数学的帰納法と背理法 第２講【限られた素因数しかもたないことの証明】【2007年度 東北大学】
問題はこちら（画像をクリックするとPDFファイルで開きます。） 「数学的帰納法と背理法」シリーズの２弾目です。 このシリーズの一覧はこちら 今回のオチは「共通素因数がこれしかない」ということの証明です。 前回の「互いに素(共通素因数をもたない)」ということと本質的には同じですので、前回の問題ができなかった人はリベンジしてみてください。 解答はコチラ
続きを読む
数学的帰納法と背理法 第３講【仮定の工夫】【2012年度 和歌山県立医科大学】
問題はこちら（画像をクリックするとPDFファイルで開きます。） 「数学的帰納法と背理法」シリーズの３弾目です。 このシリーズの一覧はこちら 基本的なシナリオは前回までとおおよそは同じなのですが ココがポイント 互いに素（最大公約数が１）ということをどう翻訳するか が山場となります。 互いに素ということの翻訳の仕方は様々あるということを、本問を通じて学んでほしいと思います。 解答はコチラ
続きを読む
数学的帰納法と背理法 第４講【隠れた補題に気が付けるか】【2004年度 名古屋大学】
問題はこちら（画像をクリックするとPDFファイルで開きます。） 「数学的帰納法と背理法」シリーズの４弾目です。 このシリーズの一覧はこちら 本問は前回までのシナリオをベースとしながらも、さらに見抜くべきことや示すべきことが多々あります。 「数学的帰納法と背理法３」の記事で、「互いに素であることの翻訳の仕方は色々ある」ということを勉強したと思います。 「２数が互いに素である」ということは「その２数の最大公約数が１」と翻訳することが基本です。 最大公約数を扱うにあたり、大きな武器が ...
続きを読む
数学における２大証明法「数学的帰納法」と「背理法」のコラボレーション問題です。
指導者側からすると「ハイハイこれね」と言いたくなるぐらい手垢のついた問題ですが、初めて解いた時の気持ちよさは今でも覚えています。
漸化式に関する証明問題では帰納法を用いるのが常套手段です。
本問では「互いに素」であることを証明するために背理法を用いることになります。
矛盾の仕方が個人的に気持ちいいですね。
(以下ネタバレ注意)
+ クリック（タップ）して続きを読む
(1) について
元々、この数列の定義の仕方から \(a_{n+1}\) , \(b_{n+1}\) を考えるにあたっては
\(x^{n+2}\) を \(x^{2}-x-1\) で割った余りを考えることになります。
\(a_{n}\) , \(b_{n}\) と絡めようと思うと
\(x^{n+1}=(x^2-x-1)Q(x)+a_{n}x+b\)
の両辺に \(x\) をかけることにより
\(x^{n+2}=(x^2-x-1) \ xQ(x)+a_{n}x^{2}+bx\)
と見ていきます。
\(a_{n}x^{2}+bx\) からは、まだ無理やりにでも \(x^{2}-x-1\) を括ることができると判断して
\(a_{n} (x^2-x-1)+(a_{n}+b_{n})x+a_{n}\)
と見れれば、解決したようなものです。
(2) について
漸化式によって定まる数列についての証明問題では数学的帰納法が最有力の路線です。
\(a\) , \(b\) が互いに素であるとは
\(a\) , \(b\) の最大公約数が \(1\) である
ということですが、これをもう少し踏み込んで考えれば
\(a\) , \(b\) が 2 以上の公約数をもたない
という否定的な内容です。
したがって帰納法の中で、背理法を用いることを考えたいところです。
解答はコチラ
