Number of reachable vertices in a tree Given a tree $T$ with infinite nodes. Each node of the tree has exactly $C$ children. I need to figure out that, starting from a node at distance $h$ from root, how many distinct vertices can be reached in exactly $k$ steps? A step from a node is a jump to any adjacent vertex. 
Thanks for any help.
 A: Without backtracking
Every node except the root has degree $C+1$. If $k\leq h$, there are $$(C+1)C^{k-1}$$ reachable nodes. If $k>h$, then we have to worry about paths traversing the root. One formula is $$C^k + \sum_{j=1}^h (C-1) C^{k-j-1}.$$ The $C^k$ counts paths going down (away from the root.) Each term $(C-1) C^{k-j-1}$ counts paths going $j$ steps upward, then choosing from the other $(C-1)$ children of the $j$th ancestor, then taking the remaining $k-j-1$ steps down.
This can be simplified as $$C^k +C^{k-1}-C^{k-h-1}.$$
With backtracking
If backtracking is allowed, then in $k$ steps we can reach any vertex at the end of a path of length $k$, or a path of length $k-2$, or by any path whose length is less than $k$ and the same parity as $k$.
So, if $k \leq h$ and $k = 2n+1$ is odd, we have
$$\sum_{j=0}^n (C+1)C^{2j}$$
vertices. This can be rewritten as
$$
(C+1)\frac{C^{2n+2}-1}{C^2-1}
= \frac{C^{k+1}-1}{C-1}.
$$
If $k = 2n$ is even (and still $k \leq h$), we have
$$1 + \sum_{j=1}^n (C+1)C^{2j-1}$$
reachable vertices.
This again simplifies to $$\frac{C^{k+1}-1}{C-1}.$$
If $k > h$, and $k$ and $h$ have the same parity, then we have
$\frac{C^{h+1} - 1}{C-1}$ nodes reachable in 
$k$ steps at distance $h$ or less,
and $\sum\limits_{l=1}^{\frac{k-h}{2}} (C^{h+2l} + C^{h + 2l - 1} - C^{2l-1})$ reachable at distance more than $h$. When added and simplified, this is
$$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - 1}{C^2 -1}.$$
On the other hand, if $k > h$ and $k$ and $h$ have different parity, then we have
$$\frac{C^{h} - 1}{C-1} + \sum_{l=0}^{\frac{k-h-1}{2}} \bigl(C^{h+2l+1} + C^{h + 2l} - C^{2l}\bigr),$$
which simplifies to
$$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - C}{C^2 -1}.$$
Another approach when $k > h$
We can also just take the $\frac{C^{k+1}-1}{C-1}$ vertices which would be reachable if every node had degree $C+1$, and subtract those which would be found in the missing branch at the root.
If $k$ and $h$ have the same parity, this is
$$\frac{C^{k+1}-1}{C-1} - \sum_{j=0}^{\frac{k-h-2}{2}} C^{2j+1},$$
which simplifies to the same expression as before,
$$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - 1}{C^2 -1}.$$
If $k$ and $h$ have different parity, we have
$$\frac{C^{k+1}-1}{C-1} - \sum_{j=0}^{\frac{k-h-1}{2}} C^{2j},$$
which simplifies to the same expression as before,
$$ \frac{C^{k+2} + C^{k+1} - C^{k-h+1} - C}{C^2 -1}.$$
A: Considering your question, it can be seen that for h>=k, the answer will be:
$$
(C^{k+1}-1)/(C-1)
$$
