質問：
再代入を使用して、次の漸化式を解きます。
T（N）= 2T（n-1）+ n; n> = 2およびT（1）= 1
これまでのところ私はこれを持っています：
T（n）= 2T（n-1）+ n
= 2（2T（n-2）+（n-1））+ n
= 4T（n-2）+ 3n -2
= 2（4T（n-3）+ 3（n-1）-2）+ n
= 2（4T（n-3）+ 3n -3 -2）+ n
= 2（4T（n-3）+ 3n -5）+ n
= 8T（n-3）+ 6n-10 + n
= 8T（n-3）+ 7n -10
これまでのところ、私がこれにアプローチしている方法は正しいかどうか疑問に思っています。どんな助けでもありがたいです、ありがとう。
この手順は間違っています：
= 4T(n-2) + 3n -2
= 2(4T(n-3) + 3(n-1) -2) + n
そのはず
= 4T(n-2) + 3n -2
= 4(2T(n-3) + (n-2)) + 3n - 2
T(n-i)をに置き換えます2T(n-i-1) + (n-i)。
それとは別に、私はあなたがこれを間違えていると思います。あなたの先生があなたにしてほしいことは、その価値がどうなるかを感じるT(n)ことです。この場合、反復するたびに、最初の係数に。を掛け、2最後に。のようなメンバーがあることがわかりますan+b。これはT(n) = 2^n + O(n)、最大のメンバーだけが重要だからです。