# Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289

Please have a look at this paper, specifically page 18 in which he tries to prove his lemma that $R_{0,n-1} \leq R_{0,n}$ here $R$ refers to the minimal optimal node which will be the root of the binary tree containing elements $a_{0} ... a_{n}$ .

I understood the idea of the proof using induction that for some $k \, j_{k}=i_{k}$ . Now the next part of the proof is cutting and replacing,I have understood perfectly till there. What i don't understand is how $F''$ weighted path length is equal to weighted path length of $F'$ for all $a_{n}$. Can anyone please give me a hint or a solution to that.

I am thinking if jk = ik, let's denote jk=ik=m, then we think of subsequences of [0,m-1] and [m+1,n], treat [m+1,n] as a standalone tree. And according to the paper, T and T' will be of same weighted path length if αn = α. So let's make a tree of subsequence [m+1,n] with last item being α, with weighted path length sum being Tk. And then replace the right-subtree of jk/ik with Tk for both T and T'.
Let's denote the weighted path length sum of [0, m-1] of T and T' being T0 and T0'. Because jk = ik, the levels of T and T' are both k. SoC(T) = T0 + k*Ak + Tk(starting from level k+1); C(T') = T1 + k*Ak + Tk(starting from level k+1); And C(T) should be equal to C(T'). So T1 = T1'
PS: actually I don't quite know how it proves j2<=i2, j3<=i3 using induction and left-right symmetry, anyone can help answer that?