本当に馬鹿なので問題文を忘れてました。
「下記のrecurrence relations(回帰関係？？？)を解け」でした。

実はもう一問あります。こっちは全然分かりませんが
また自力でやったので間違いを指摘してやって下さい。
お願いします。m(__)m

{x(1)=1
{x(n)=x(n/2)+n, n>1 a power of 2 (n=2^k)
もしnが十分に大きいなら、代入を繰り返すことによって
x(n)=x(n/2)+n
=(x(n/4)+n/2)+n
=x(n/4)+n/2)+n
=(x(n/8)+n/4+n/2)+n
=x(n/8)+n/4+n/2+n
それゆえに、i回の代入の後、
x(n)=x(n/2^i) + n/2^(i-1) + n/2^(i-2) + n/2(i-3)
　　　　　　i-1
=x(n/2^i) Σn/2^j ① ←これが合っているか自信がありません…
　　　　　　j=0

私達は帰納法によって①が正しいことが証明できる
i=1の場合は普通に正しい
i>1の場合は…分かりません。助けてください。m(__)m

今、①が正しいことが証明された(ことにする)
i=n-1と仮定すると
　　　　　　　　　　(n-1)-1
x(n)=x(n/2^(n-1)) Σn/2^j
　　　　　　　　　　j=0
…もしかしてlog nとか出る奴ですか…もう限界です。
どうか助けてやって下さい。m(__)m