How to show the average calculation of binary search trees

I don't understand the explanation that "assume a solution and use inductive methods to show its correctness," or more specifically, you don't fully understand what inductive methods are.

Using the formula 'The sum of natural numbers from 1 to n is (n*(n+1)/2)', show what inductive proof is like.
(A natural number is an integer greater than zero.1,2,3,4,5,...)

To show that this formula is correct (n can be any natural number),
　(a) If n is 1, correct (1*(1+1)/2=(1*2)/2=2/2=1
　(b) If n is correct when X, then n is correct when X+1
It is sufficient to show two things:

(a) shows that n is the smallest natural number of 1 and
(b)And since n is correct when n is 1, n is correct when n is 2.
Furthermore, in (b), n is correct when n is 2, so n is correct when n is 3. Repeated use of (b) such as ... indicates that all natural numbers are valid.

In this way,
·It can be established with a certain value and
"·Even if the value is changed (in the example above, ""increase by one"", it is still valid."
·By changing the value repeatedly ("increase by one"), the range within which the formula can be applied can be generalized
The method of formal proof in is called induction.

===
Let's think about binary tree exploration.
A binary tree is a tree structure in which a node has a value such that "left child value A binary tree search is a binary tree search that follows a node for the first time from the root node until it matches the value it looks for.The calculated amount is the number of times the values were compared before a matching node was found.

If the tree height is M, the number of nodes is (2^M)-1.
Since the number of nodes is almost 2 M times, the height of the left and right bifurcated trees with the number of nodes n is approximately log2(N).log2 is a logarithm with a base of 2.
The height of a binary tree is the upper limit (worst value) of the calculated amount, so for a bifurcated tree, the upper limit of the calculated amount is O(log(N)).Equal left and right means minimum calculation limits.

The maximum computational limit is a bifurcated tree (a straight tree) with only one branch extended, and the maximum computational limit is N.

The upper limit was assumed to be considering both cases so that it could be dominant.

T(n)<=alogn+b

That's the formula.
A*log(n) is the upper limit if the part is equal to the left and right, and b is the upper limit if the branch is only extended to one side, and the addition of both means that neither of them is less than the actual upper limit.

Values such as a and b are undecided at the start of inductive proof.

For example, if there is only one node in a binary tree, the calculation amount (T(n)) is 1 (only one node to compare), the number of nodes (n) is 1, the upper limit (b) is 1, and log2(0) is 1.
As T(1)=a*0+1=1, it is established when T(n)<=alogn+b is n=1.(At that time, b is 1)

< 画像 Regarding the part where <= is indicated in the formula below the image.>
Because alogn+b is the upper limit of the calculation amount (T(n)) , the upper limit of T(n)< calculation amount (alogn+b) is established.
However, in some cases, an equal sign is established as shown in (2).
Therefore, instead of "<", "<="

==
If you think about it in this way, you will understand it.

The answers are quite long and contain formulas, so I will make a PDF of the answers and attach a link to them.
For your reference
Link to Answer PDF
https://drive.google.com/open?id=1QHhrCu4-2Sn48rYnyawEruyxINansKCg

To be honest, I think it would be easier to read this book if you studied at least enough to complete the end-of-chapter questions before continuing to read it.