A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices 
Proposition: A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices.
Assuming that $d > 2$ and $k > 3$, improve the bound in above proposition to $d^k$.

The above question is from exercise problem in Diestel's book. How can we formally prove this?
 A: Let $v$ be a central vertex of the graph. This has at most $d$ neighbors. Each neighbor has at most $(d-1)$ other neighbors, for at most $d(d-1)$ total new vertices. Each of these neighbors has at most $(d-1)$ other neighbors, for $(d-1)^2d$ total new vertices. Continuing in this fashion, you get the summation
$$
1+ d + d(d-1) + d(d-1)^2 +d(d-1)^3+\dots = 1+\sum_{i=0}^{k-1}d(d-1)^i
$$
Note that the summation stops at $k$, because the distance from $v$ to any other vertex is at most $k$.
A: Let $G(V,E)$ be a simple graph with radius at most $k$ and maximum degree at most $d$.  Fix a center $u\in V$ of $G$ (i.e., any path from $u$ to another vertex of $G$ is of length at most the radius of the graph).  A vertex $v\in V$ is of level $l\in\{0,1,2,\ldots,k\}$ if the shortest path from $u$ to $v$ is of length $l$.  Write $N_l$ for the number of vertices of level $l$.
First, $N_0=1$.  Thus, $N_1\leq d$.  We can easily seen that $$N_{l+1}\leq (d-1)\,N_l\text{ for }l=1,2,\ldots,k-1\,,$$ because a vertex of level $l+1$ must be joined by an edge to a vertex of level $l$, and each vertex of level $l$ can is adjacent to at most $d-1$ vertices of level $l+1$, having one edge connected to a vertex of level $l-1$.  That is,
$$N_{l}\leq d\,(d-1)^{l-1}\text{ for }l=1,2,3,\ldots,k\,.$$
If $d>2$, then
$$\begin{align}
|V|&= \sum_{l=0}^k\,N_l\leq 1+d\,\sum_{l=1}^k\,(d-1)^{l-1}\leq 1+kd(d-1)^{k-1}\leq 1+kd^k\,.
\end{align}$$
If $d=2$, then obviously, $N_l\leq 2$ for all $l=1,2,\ldots,k$, whence
$$|V|\leq 1+2k\leq 1+kd^k\,.$$
If $d=1$, then the graph consist of at most $2$ vertices, so
$$|V|\leq 2\leq 1+kd^k\,,$$
as $k\geq 1$.
The inequalities
$$|V|\leq 1+d\,\sum_{l=1}^k\,(d-1)^{l-1}=\left\{
\begin{array}{ll}
1+d\left(\frac{(d-1)^k-1}{(d-1)-1}\right)\,,&\text{ for }d\neq 2\,,\\
 1+2k\,,&\text{ for }d=2\,,\end{array}\right.$$
are sharp, and stronger than the original inequality $|V|\leq 1+kd^k$.  An example in each case should be easy to find.  We can also show that $|V|< d^k$ for $d\geq 2$ and $k\geq 3$.  The case $d=2$ is trivial. For $d>2$, we note that
$$\begin{align}(d-2)\,\left(\frac{d^k-1}{d}\right)&> (d-2)\,\left(d^{k-1}-1 \right) = d^2(d-2)\,d^{k-3}-(d-2)
\\
&> \left((d-1)^3+d^2\right)\,d^{k-3}-(d-2)\geq (d-1)^3\,d^{k-3}+d^2-(d-2)
\\
&>(d-1)^3\,d^{k-3}-1\geq (d-1)^k-1\,,\end{align}$$
whence
$$|V|\leq 1+d\,\left(\frac{(d-1)^k-1}{d-2}\right)<d^k\,.$$
