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.
 A: 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.
