うさぎでもわかる離散数学　番外編1　数学的帰納法

数学的帰納法で示す。
(1) \( n = 2 \) のとき、\[ (左辺) = 3^2 = 9 \\ (右辺) = 2 \cdot 2^2 = 8\] より、（左辺）>（右辺）となり、\( n = 2 \) のときは成立する。

(2) \( n = k \ \ (k \geqq 2) \) のとき、\( 3^k \gt k 2^k \) 、つまり \( 3^k - k 2^k \gt 0 \) が成立すると仮定する。

\( n = k + 1 \) のとき、\( 3^{k+1} \gt (k+1)2^{k+1} \) 、つまり \( 3^{k+1} - (k+1)2^{k+1} \gt 0 \) が成立することを示す。\[ \begin{align*} &
3^{k+1} - (k+1)2^{k+1} \\ = &  3 \cdot 3^k - (2k +2) \cdot 2^k 
\\ = & 3 \cdot 3^k -  (2k +2) \cdot 2^k
\\ = & 3 \cdot 3^k - 3k \cdot 2^k + (k - 2) \cdot 2^k
\\ = & 3(3^k - k \cdot 2^k) + (k - 2) \cdot 2^k \gt 0
\end{align*}  \]ここで、仮定より \(  (3^k - 3k \cdot 2^k) \gt 0 \) である。
さらに、\( k \geqq 2 \) より、\( (k - 2) \cdot 2^k \geqq 0 \) である。
よって、 \( n = k+1 \) のときも成立。

(1),(2)より題意は満たされた。

こんな感じに解法を忘れてしまって推測して答えを出そうとするのはいい考えなのですが、この場合だと \( a_7 \) 以降が正しい答えになるのかが書かれていないため、記述式だとかなりの減点をくらってしまいます。

そんなときに役に立つのが帰納法です。答えを推測し、その答えが合っていることを帰納法で証明してしまえばいいのです！　今回は上の \( a_n = 3^{n-1} + 1 \) を証明してみましょう。

数学Aの整数問題みたいな問題も帰納法で証明できてしまいます。