>>366
基本的な漸化式の解法を復習してみよう
①　a[n+1] = a[n]
②　a[n+1] = a[n] + 2
③　a[n+1] = a[n] + n
④　a[n+1] = a[n] + 2^n
⑤　a[n+1] = 2*a[n]
⑥　a[n+1] = 2*a[n] + 2
⑦　a[n+1] = 2*a[n] + n
⑧　a[n+1] = 2*a[n] + 2^n

① a[n] = a[1]
② a[n] = 2*(n-1) + a[1]
③ a[n] = (1/2)*n(n-1) + a[1]
は、辺々足し算して導き出すよね
④も同じく足していくと、a[n] = a[1] + 2 + 2^2 + 2^3 +・・・+ 2^(n-1)
となって、2 + 2^2 + 2^3 +・・・+ 2^(n-1) の部分は、2*(2^(n-1) - 1)/(2-1)、
あるいは、1を足して、1 + 2 + 2^2 + 2^3 +・・・+ 2^(n-1) = (2^n -1)/(2-1) - 1、
つまり、a[n] = 2^n - 2 + a[1] になる

⑤は、辺々掛け算して、a[n] = 2^(n-1) * a[1] だ
⑥は、a[n+2] = 2*a[n+1] + 2 でもあるから、元の式で辺々引くと、
a[n+2] - a[n+1] = 2*(a[n+1] - a[n])
これは、b[n+1] = a[n+2] - a[n+1] とおくと、b[n+1] = 2*b[n] となって、⑤のパターンになる
⑦も、a[n+2] = 2*a[n+1] + (n+1) でもあるから、同様に辺々引くと、
a[n+2] - a[n+1] = 2*(a[n+1] - a[n]) - 1
これは、⑥のパターンだ
⑧は、2^nで割ってみると、⑥か②のパターンになることがある
割り切れないときは、>>365の手法を使って、⑤のパターンにするといい

見慣れない漸化式は、自分の解けるパターンに、なんとかもっていくっていうことだね