「解を仮定してその正しさを帰納法で示す方法をとる」という説明が理解できない、より具体的には『帰納法』が何なのかを十分に理解していらっしゃらないのだと思われます。
『1からnまでの自然数の和は(n*(n+1))/2 で求められる』という公式を例にして、帰納法による証明がどんなものか示します。
(自然数というのは、0より大きな整数の事。1,2,3,4,5,....というような数)
この公式が正しい(nがどんな自然数であっても成立する)ことを示すには、
(a) nが1の時、正しい (1*(1+1))/2 = (1*2)/2 = 2/2 = 1
(b) nがXの時に正しければ、nがX+1の時にも正しい
の2つを示せば足ります。
(a)で、nが一番小さい自然数である1の時に成り立つことが示され、
(b)で、nが1の時に正しいのだから、nが2の時も正しい
さらに、(b)で、nが2の時に正しいのだから、nが3の時も正しい
...というように(b)を繰り返し使っていくと、すべての自然数で成立することが示せます。
このように、
・ある値で成立する事と、
・値を変更(上の例では"1増やす")しても成り立つ、
・値の変更("1増やす")を繰り返す事で、公式が適用できる範囲が一般化できる
をもって公式の証明をする方式を帰納法と言います。
===
「2分木探索」について考えてみましょう。
2分木は「左の子の値<親の値<右の子の値」が成り立つような値をノードが持つ木構造です。
2分木探索は、2分木を使った検索で、根のノードから初めて、探す値と一致するまでノードを辿っていきます。値が一致するノードが見つかるまでに値の比較をした回数が計算量になります。
2分木が左右均等である場合、木の高さがMなら、ノードの数は(2 ^ M)-1になります。
ノード数はほぼ2のM乗ですから、ノード数nの左右均等な2分木の高さは log2(N)ほどになります。log2は、2を底とする対数。
2分木の高さは、計算量の上限(最悪値)ですから、左右均等な2分木の場合は計算量の上限はO(log(N))といえます。左右均等な場合が、計算量の上限が最小です。
計算量の上限が大きいのは、一方にだけ枝が伸びた2分木(一直線状の木)で、計算量の上限はNです。
<⑴ T(n)<= alogn+bを仮定する理由について>
どちらが支配的であっても大丈夫なように両方の場合を勘案して上限と仮定されたのが
T(n)<= alogn+b
という式です。
a*log(n)の部分が左右均等な木の場合の上限値、bが一方にだけ枝が伸びた木の場合の上限値で、両方を加えたものは、どちらが支配的でも実際の上限より小さくならない事を表しています。
aやbといった値は、帰納法による証明を始める時点では未定です。
<⑵n=1のときはb=1とすれば成立する>
例えば、2分木が1つのノードだけの場合、計算量(T(n))は1(比較するノードは1個だけ)、ノードの個数(n)は1、一方に枝が伸びた木の場合の上限値(b)は1。そして、log2(0)は1。
T(1) = a*0 + 1 = 1 となるので、T(n)<= alogn+bがn=1の時に成立する。(その時のbは1)
<⑶画像下の式で<=としている箇所についてです。>
alogn+bは計算量(T(n))の上限なので、 T(n) < 計算量の上限(alogn+b)が成り立つ。
しかし、(2)のように等号が成り立つ場合もある。
なので、"<"ではなく"<="としている。
==
このような道筋で考えていくと理解できるのではないでしょうか。