nを2のべき乗とする漸化式の解き方

質問

[問題]
logの底は2、nは2のべき乗、n≧2とする。
f(n) = 2f(n/2) + log(n) + 1
f(1) = 1

という問題の解法がわからずに困っています。

自分で問題を考えたところ、n = 2^k と置き、f(2^k) = g(k) のように変換して解答できるかと思ったのですが、その場合 log(n) をどのように扱えばよいのかわかりませんでした。

n = 1, 2, 3, ... と順番に代入してみても法則は掴めませんでした。

どのようにして解けばいいかわかる人はいらっしゃいますか？
ヒントだけでも構いません。

どなたか回答をよろしくお願いします。

回答No.2

rnakamra · ベストアンサー

g(k) = 2g(k-1) + k+1
の特性方程式
x^2 - 2x - (k+1) = 0
の解をα、βとしたとき、一般解は
g(n) = c1*α^n + c2*β^n
と書け、初期条件
f(1) = 1
を利用してc1、c2を求める

α,βがkの式になってしまうのでうまくいかないのではないかな。
h(k)=g(k)-k
としてh(k)の漸化式を求めてみると良いでしょう。

お礼

h(k)の漸化式を解くことで、最終的にf(n)の漸化式を解くことができました。

回答ありがとうございました。

回答No.1

rnakamra

n=2^kとおくと
f(2^k)=2f(2^(k-1))+log[2]2^k+1=2f(2^(k-1))+k+1
です。(log[2]2^k=klog[2]2=k*1=k)

f(2^k)=g(k)とおくと
g(k)=2g(k-1)+k+1
となります。

補足

回答ありがとうございます。

f(2^k) = g(k)
とおいた続きなのですが、

g(k) = 2g(k-1) + k+1
の特性方程式
x^2 - 2x - (k+1) = 0
の解をα、βとしたとき、一般解は
g(n) = c1*α^n + c2*β^n
と書け、初期条件
f(1) = 1
を利用してc1、c2を求める

と考えました。解き方としてはこの流れで正しいでしょうか？
また、g(n)が求まった後、f(n)に戻す必要があると思うのですが、これはどうすればいいのでしょうか？

再度よろしくお願いします。