[解決済み] 解いてみてください。T(n) = T(n-1) + n [重複] とする。

質問

Cormenのアルゴリズム入門の本で、次のような問題に挑戦しています。

漸化式 T(n) = T(n-1) + n の解が O(n2 ) であることを代入を使って示せ。

(初期条件が与えられていなかったので、これが問題文の全文です)

しかし、正しい処理方法がわからないようです。教科書では簡単にしか触れられていないし、検索したほとんどのサイトでは、すでに方法を知っていることを前提にしているようです。どなたか、簡単なステップバイステップのガイド、またはそのリンクでも構いませんので、教えていただけると幸いです。

一応、今までの私の試みは以下の通りです。

T(n) <= c(n^2)
       <= c(n-1)^2 + n
       <= c(n^2 -2n +1) + n (これは < c(n^2) ではないと思うのですが...)

また、ありがとうございます。

UPDATE: 混乱を避けるために、私が達成しようとしている方法の例を示します。

解がO(nlog(n))であることを証明する。
T(n) = 2T([n/2]) + n
代入法では、定数c > 0の選択に対して、T(n) <= cn*lg(n)を証明する必要があります。この境界がすべての正のm < n、ここでm = [n/2] に対して成り立つと仮定すると、 T([n/2]) <= c[n/2]*lg([n/2]) という結果になります。これを漸化式に代入すると次のようになる。
T(n) <= 2(c[n/2]*lg([n/2])) + n
       <= cn*lg(n/2) + n
       = cn*lg(n) - cn*lg(2) + n
       = cn*lg(n) - cn + n
       <= cn*lg(n)
ここで、最後のステップは、c >=1である限り成立します。
このロジックにはうまく従えるのですが、上記の問題の手順を再現しようとすると、行き詰ってしまいます。

解決方法は？

これは誘導尋問のつもりなんでしょうか？

つまり、基本ケース n=1 はトリビアルです。 帰納的な場合、n>1 とします。 (*) T(n-1) が O((n-1)) であるとします。 ² )=O(n ² ). T(n) もまたO(n ² ).

 T(n) = T(n-1) + n
      < c (n-1)^2 + n,  assume c>1 wlog
      < c n^2 - 2cn + c + n
      < c n^2 - (2c - 1)n + c
      < c n^2

for n > 1, c > 1.

ここでブレイクアウト。

まず、c > 1のとき、2c - 1 > cであることに注意してください。

      < c n^2 - (2c - 1)n + c
      < c n^2 - (c)n + c

次に、n > 1のとき、-(c)n+c = (1-n) c < 0であることに注目します。

      < c n^2 - (c)n + c
      < c n^2

T(n) < c n^2 となるような定数 c が存在するので、明らかに T(n) は O(n) です。 ² ).

だいたいこんな感じでしょうか？ エッジケースを修正するために何度も編集しました。