⛳

113. 数学的帰納法

2023/03/22に公開

学習

tech

【問題概要】
以下の命題 $P(n)$ が $n$ についての正しい場合、 $P(k)$ が成り立つことを $n=k$ までの帰納法により証明せよ。

【解説】
この問題は、数学的帰納法によって式を証明する問題です。
帰納法とは、ある条件が $n=1$ の場合に成り立ち、かつ $n=k$ の場合に成り立つと仮定した上で、 $n=k+1$ の場合にも成り立つことを証明する方法です。

今回の式 $P(n)$ を示すには、まず $n=1$ の場合に式が成り立つことを示し、次に $n=k$ の場合に式が成り立つと仮定した上で、 $n=k+1$ の場合にも式が成り立つことを示せばよいです。

具体的には、 $n=1$ の場合には、左辺は $1^2=1$ 、右辺は $\frac{1\times(1+1)\times(2\times1+1)}{6}=1$ となり、式が成り立ちます。

次に、 $n=k$ の場合に式が成り立つと仮定すると、 $n=k+1$ の場合にも式が成り立つことを示します。

この式を変形すると、以下のようになります。

このように、 $n=k+1$ の場合にも式が成り立つことが示されました。

よって、帰納法により、式 $P(n)$ が正しいことが証明されました。

AtCoderの類題: 「数列としての式展開 / Sequence」 https://atcoder.jp/contests/abc181/tasks/abc181_c
レーティング難易度(★): 900
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1393-2063
レーティング難易度(%): 44.9%
レーティング(数値): 1963
AC率(%): 44.9%
ACしたスコアの高い回答者: tourist (2601)
解説ブログ: https://img.atcoder.jp/abc181/editorial

「Frog 1」

レーティング難易度(★): 2
ACした回答者に絞った場合のレーティング帯の範囲(数値): 0~1499
レーティング難易度(%): 84.7
レーティング(数値): 805
AC率(%): 54.7
ACしたスコアの高い回答者: https://atcoder.jp/users/square1001
解説ブログ: https://www.hamayanhamayan.com/entry/2019/01/12/200447

「ABC137 D - Summer Vacation」

レーティング難易度(★): 6
ACした回答者に絞った場合のレーティング帯の範囲(数値): 800-2400
レーティング難易度(%): 23.8%
レーティング(数値): 1741
AC率(%): 23.8%
ACしたスコアの高い回答者: -
解説ブログ: https://www.hamayanhamayan.com/entry/2018/08/26/002115