Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 7 more comments

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.