Let T(n) be the number of different binary search trees on n distinct…

Concept — in a binary search tree every key smaller than the root lies in its left subtree and every key larger than the root lies in its right subtree. Fixing which key sits at the root therefore splits the remaining keys into two groups that can never exchange members, and those two subtrees are then shaped completely independently of each other. By the product rule, the number of trees for one fixed root is (ways to shape the left group) × (ways to shape the right group), and the total number of trees is the sum of that product over every key that is allowed to be the root.

Applying it to this recurrence:

1. Sort the n distinct keys in increasing order and let the k-th smallest key be the root, for one fixed k in the range 1 to n.

2. Exactly k-1 keys are smaller than that root, and all of them must sit in the left subtree, so the left subtree can be shaped in T(k-1) ways.

3. Exactly n-k keys are larger than that root, and all of them must sit in the right subtree, so the right subtree can be shaped in T(n-k) ways.

4. The left and right shapes are chosen independently, so the number of BSTs whose root is the k-th smallest key is T(k-1) × T(n-k).

5. Every BST has exactly one root, so the n cases k = 1, 2, …, n are disjoint and together cover every tree: T(n) = the sum over k = 1 to n of T(k-1) × T(n-k).

6. Comparing this with the given form T(n) = the sum over k = 1 to n of T(k-1) × T(x) shows that x is n-k.

Cross-check:

• Counting the parts: (k-1) keys on the left, 1 key at the root and (n-k) keys on the right add up to n keys, so every key is placed exactly once.

• Boundary case k = n: the largest key is the root and the right subtree is empty, so the second factor has to be T(0). The value n-k is 0 there, and T(0) = 1 is the empty-tree convention that keeps the sum consistent.

• Numerical check for n = 3: T(3) = T(0)T(2) + T(1)T(1) + T(2)T(0) = 1×2 + 1×1 + 2×1 = 5, which matches the 5 binary search trees on 3 distinct keys — the Catalan number C3.

So x is n-k. The recurrence T(n) = the sum over k = 1 to n of T(k-1) × T(n-k), with base cases T(0) = T(1) = 1, is the Catalan recurrence, and T(n) is the n-th Catalan number.