オーダー記法：ちょっとしたクイズ

1+2+...+n = O(n) となることをいまから証明しますが，もちろんこれは間違っています．
(真実は 1+2+...+n = n(n+1)/2 なので．)
どこがまちがっているでしょう？というのがクイズです．

証明

nに関する数学的帰納法．
n=1のとき，左辺は1で右辺はO(1)．1=O(1)なので成立．
n>1のときを考えると，1+2+...+n=(1+2+...+(n-1))+n = O(n-1)+n = O(n)+n = O(n)．
ここで，「1+2+...+(n-1)=O(n-1)」という帰納法の仮定を用いた．
証明終

このクイズはいろいろ示唆に富んでると思うのです．考えてみてください．
(誰に向かって言ってるのか不明ですが．)

オーダー記法：ちょっとしたクイズ補遺

上の書き込みのクイズのヒント (になるかどうか分からないけどとりあえず思いついたので書きます)．

1+2+...+n = O(n^2) となることをいまから証明しますが，この式は正しいです．(1+2+...+n = n(n+1)/2 なので．)
では，下の証明は正しいのでしょうか？というのがクイズです．
(注意：言明が正しくてもその証明が正しいとは限りません．論理展開に穴があれば証明自体は正しくないわけです．)
ちなみに「n^2」というのは「nの2乗」を表わします．(LaTeX風の記法です．)

証明

nに関する数学的帰納法．
n=1のとき，左辺は1で右辺はO(1)．1=O(1)なので成立．
n>1のときを考えると，1+2+...+n=(1+2+...+(n-1))+n = O((n-1)^2)+n = O(n^2)+n = O(n^2)．
ここで，「1+2+...+(n-1)=O((n-1)^2)」という帰納法の仮定を用いた．
証明終