To show that if every internal node in tree T has exactly 3 children, then nE = 2nI + 1, we can use the following proof by induction:

Base Case:

For a tree with only one internal node and no external nodes, nI = 1 and nE = 0.

Plugging these values into the equation nE = 2nI + 1 gives 0 = 2(1) + 1, which is true.

Inductive Hypothesis:

Assume that for a tree with k internal nodes, where every internal node has exactly 3 children, the equation nE = 2nI + 1 holds true.

Inductive Step:

Now, consider a tree T' with k + 1 internal nodes, where every internal node has exactly 3 children.

Let's denote the number of external nodes in T' as nE' and the number of internal nodes as nI'.

We can think of T' as being formed by adding a subtree to an existing tree T, which has k internal nodes.

The additional subtree must be attached to one of the external nodes of T, resulting in the addition of one internal node and three external nodes.

The number of internal nodes in T' is nI' = nI + 1, as we have added one internal node.

The number of external nodes in T' is nE' = nE + 3, as we have added three external nodes.

Using the inductive hypothesis, we can substitute nE = 2nI + 1 for T into the equation for T':

nE' = nE + 3 = (2nI + 1) + 3 = 2nI + 4 = 2(nI + 1) + 2 = 2(nI' - 1) + 2 = 2nI' + 1

This shows that the equation nE = 2nI + 1 holds true for the tree T'.

By the principle of mathematical induction, the equation holds true for any tree T where every internal node has exactly 3 children.

Therefore, if every internal node in T has exactly 3 children, nE = 2nI + 1.