# Prove $n_0=(k-1)n_k+(k-2)n_{k-1}+\dots+3n_4+2n_3+n_2+1$

I want to prove $$n_0=(k-1)n_k+(k-2)n_{k-1}+\dots+3n_4+2n_3+n_2+1$$ for T as a binary tree where $n_i$ is nodes of degree $i$. I tried to prove it using the handshake lemma but came up with nothing useful.

-
I found this question while searching for duplicates, the notations are close but not exactly the same plus that my question is about binary trees. –  Gigili Dec 17 '11 at 11:02
Do you mean there are $n_i$ nodes of degree $i$? What do you mean by degree BTW? –  user17090 Dec 17 '11 at 11:06
@AliBleybel: For instance, $n_0$ is the number of leaves, nodes of degree 0. –  Gigili Dec 17 '11 at 11:14
You should check your notation: the terms left of '...' do not correspond to those on the right (or you'd have 2n_3 + n_1 as coefficients); and the double n_2 at the end seems wrong too. –  gnometorule Dec 17 '11 at 11:19
@gnometorule: Right, sorry about that. –  Gigili Dec 17 '11 at 11:23

We want to prove that if $T$ is any tree, and $n_k(T)$ is the number of nodes of $T$ with $k$ children, then $$n_0(T)=1+\sum_{k\ge 2}(k-1)n_k(T)\;.\tag{1}$$ Note for future reference that the righthand side can be written $$1+\sum_{k\ge 1}(k-1)n_k(T)\;,$$ since the $k=1$ term is $0$.

Added: I realized after I went to bed that there’s a short argument that doesn’t use induction. Let $T$ be a tree with $n$ vertices and $e$ edges. Then $$n=\sum_{k\ge 0}n_k(T)\;,$$ and $$e=\sum_{k\ge 1}kn_k(T)\;,$$ since a non-leaf node with $k$ children produces $k$ edges connecting it to those children. But in any tree $n=1+e$, so $$\sum_{k\ge 0}n_k(T)=n=1+e=1+\sum_{k\ge 1}kn_k(T)\;,$$ and subtracting $\sum\limits_{k\ge 1}n_k(T)$ from both sides leaves $$n_0(T)=1+\sum_{k\ge 1}kn_k(T)-\sum_{k\ge 1}n_k(T)=1+\sum_{k\ge 1}(k-1)n_k(T)\;.$$ I’ve kept the original proof below, however, as it embodies a useful technique.

This can be done by induction on the number of nodes in $T$. It’s clearly true for the tree with just one node, since in that case it says that $1=1$. Suppose that $n>1$, and it’s true for all trees with fewer than $n$ nodes. Let $T$ be a tree with $n$ nodes, and let $v$ be any leaf of $T$. Since $n>1$, $v$ is not the root of $T$; let $u$ be the parent of $v$, and let $m$ be the number of children of $u$. Let $T\,'$ be the tree obtained from $T$ by removing the leaf $v$ and its adjacent edge. There are two possibilities.

If $m=1$, $u$ is a leaf of $T\,'$, and $n_0(T\,')=n_0(T)$. But this is fine: the only vertex whose number of children changed in passing from $T$ to $T\,'$ is $u$, and it had only one child to begin with, so it wasn’t counted in $(1)$ anyway, and therefore $$1+\sum_{k\ge 1}(k-1)n_k(T)=1+\sum_{k\ge 1}(k-1)n_k(T\,')\;.$$ Thus, $$n_0(T\,')=n_0(T)=1+\sum_{k\ge 1}(k-1)n_k(T)=1+\sum_{k\ge 1}(k-1)n_k(T\,')\;,$$ as desired.

If $m>1$, the tree loses a leaf without gaining one, and $n_0(T)=n_0(T\,')+1$. It also loses a node with $m$ children but gains one with $m-1$ children, so $$n_m(T)=n_m(T\,')+1\;,$$ and $$n_{m-1}(T)=n_{m-1}(T\,')-1\;.$$ Thus,

\begin{align*} (m-2)n_{m-1}(T)+(m-1)n_m(T)&=(m-2)\big(n_{m-1}(T\,')-1\big)+(m-1)\big(n_m(T\,')+1\big)\\ &=(m-2)n_{m-1}(T\,')+(m-1)n_m(T\,')+1\;. \end{align*}

$n_k(T)=n_k(T\,')$ for $k<m-1$ and $k>m$, so

\begin{align*} \sum_{k\ge 1}(k-1)n_k(T)&=\sum_{k=1}^{m-2}(k-1)n_k(T)\\ &\qquad\qquad+(m-2)n_{m-1}(T)+(m-1)n_m(T)\\\\ &\qquad\qquad+\sum_{k>m}(k-1)n_k(T)\\ &=\sum_{k=1}^{m-2}(k-1)n_k(T\,')\\ &\qquad\qquad+(m-2)n_{m-1}(T\,')+(m-1)n_m(T\,')\color{red}{+1}\\\\\ &\qquad\qquad+\sum_{k>m}(k-1)n_k(T\,')\\ &=\sum_{k\ge 1}(k-1)n_k(T\,')\color{red}{+1}\;. \end{align*}

Thus, \begin{align*} n_0(T)=n_0(T\,')+1&=\left(1+\sum_{k\ge 1}(k-1)n_k(T\,')\right)+1\\ &=1+\left(\sum_{k\ge 1}(k-1)n_k(T\,')\color{red}{+1}\right)\\ &=1+\sum_{k\ge 1}(k-1)n_k(T)\;, \end{align*} again as desired.

-
Actually, I don't get how you got the result $\sum_{k\ge 1}(k-1)n_k(T)=\sum_{k\ge 1}(k-1)n_k(T\,')+1\$ from the previous line, and then the other line after it. –  Gigili Dec 17 '11 at 14:53
@Gigili: I’ve added some extra detail to help with the first bit and fixed the typo that probably caused you trouble with the last bit. I’ve also added a shorter, non-inductive proof that occurred to me after I went offline. –  Brian M. Scott Dec 17 '11 at 21:24
Perfect, thank you. –  Gigili Dec 18 '11 at 2:21