I already know and proved the following statement:
Let $B$ be a binary tree and we want an extended binary tree. Then the following equation holds:
$$ E = I + 2 \cdot |V| $$ where $E$ is length of the external path and $I$ is the length of the internal path.
I want a statement more general:
So let us say that we have a tree $B_k$ ( $ k \geq 2$), where every node has up to $k$ childern. We extend that tree, so every node has exact $k$ children. Now I am searching for a equation between the length of the external and internal length.
Could it be :
$$ E = I + k|V|$$
or what do you think? If my assumption is true can you tell me how I can prove this? My idea would be induction. For $k=2$ I have already shown this statement. but which argument could I choose for "$k \rightarrow k+1$" ? Or do you think I should use a contructive proof like I did with the statement about binary trees?
The correct generalization is $$E = (k-1)I + k|V|.$$ To prove this, induct on the number of internal nodes of the extended tree $B_k'$; equivalently, the number of nodes $|V|$ of the original tree $B_k$.
When $|V|=1$, $B_k'$ has one internal node (the root) and $k$ external nodes which are its children. The internal path length is $0$ and the external path length is $k$, so $E = (k-1)I + k|V|$ holds.
When $|V|>1$, consider what happens when we remove a leaf node $v$ of $B_k$: in $B_k'$, this has the effect of replacing an internal node $v$ and its $k$ external children $w_1, w_2, \dots, w_k$, by a single external node $w$. If $\ell_v$ is the path length from the root to $v$, then we've reduced the internal path length by $\ell_v$, the external path length by $k(\ell_v + 1)$, and $|V|$ by $1$, but then increased the external path length by $\ell_w = \ell_v$. So the new values of $E, I, |V|$ are \begin{align} E^- &= E - k(\ell_v + 1) + \ell_v = E - (k-1)\ell_v - k, \\ I^- &= I - \ell_v, \\ |V^-| &= |V| - 1. \end{align} By the inductive hypothesis, $E^- = (k-1)I^- + k |V^-|$, and therefore $$ E - (k-1)\ell_v - k = (k-1)(I - \ell_v) + k(|V|-1). $$ This simplifies to $E = (k-1)I + k|V|$, as desired. By induction, this holds for trees of any order $|V|$.
For people like me who were puzzled by the terminology, see this for an explanation. To summarize: in rooted tree $B_k$, every node has up to $k$ children. To extend it, we construct the rooted tree $B_k'$ in which we add leaves to every node with fewer than $k$ children, until every node of $B_k$ has $k$ children. In $B_k'$, every node either has $k$ children (and is called an internal node - these are the nodes of $B_k$) or $0$ children (and is called an external node - these are the added nodes). The internal path length is the sum, over all internal nodes, of the distance to the root. The external path length is the same sum, but over all external nodes.