How can I prove that the Wiener index of the hypercube graph is $k \cdot 4^{k-1}$? I'm trying to find the Wiener index of the Hypercube graph, $Q_k$. In case anyone does not know what that is, it's a graph where every vertex is labelled by a binary $k$-tuple, and where two vertices are connect only if the tuples differ in only one place. So for example, $Q_2$ would have vertices labelled $(0, 0), (0, 1), (1, 0)$ and $(1, 1)$. $(0, 0)$ would be connected to $(0, 1)$ and $(1, 0)$, and so on.
I wrote out a few examples and I think that the Wiener index of the graph can be represented by $k \cdot  4^{k-1}$. But how do I prove this? The only idea that occurs to me is to use induction, but I am not entirely sure how to go about doing this. Any help with this would be appreciated. If anyone has any other ideas for a proof, that would be fine too.
 A: Consider the vertex $\mathbf 0=(0,0,\dots,0)$ of the hypercube graph $Q_n$. For each $r\in[n]=\{1,2,\dots,n\}$ there are $\binom nr$ vertices at a distance of $r$ from $\mathbf 0$, so$$\sum_{v\in V(Q_n)}\operatorname{d}(\mathbf 0,v)=\sum_{r=1}^nr\binom nr.$$Since all vertices of $Q_n$ are similar, the Wiener index of $Q_n$ is equal to$$\frac12\sum_{u\in V(Q_n)}\sum_{v\in V(Q_n)}\operatorname{d}(u,v)=\frac12\cdot2^n\sum_{r=1}^n r\binom nr=2^{n-1}\sum_{r=1}^n r\binom nr.$$Differentiating the binomial identity$$\sum_{r=0}^n\binom nrx^r=(1+x)^n$$we get$$\sum_{r=1}^n r\binom nrx^{r-1}=n(1+x)^{n-1};$$on setting $x=1$ we have$$\sum_{r=1}^n r\binom nr=n2^{n-1},$$and so the Wiener index of $Q_n$ is equal to$$2^{n-1}\sum_{r=1}^n r\binom nr=2^{n-1}\cdot n2^{n-1}=n4^{n-1}.$$
A: For any two graphs $G$ and $H$ we have $$ W(G \square H ) = |V(G)|^2 W(H) + |V(H)|^2W(G),$$ where $W(G)$ is the Wiener index of $G.$
Now the hypercube graph $Q_k = Q_{k-1} \square K_2$ and the result now immediately follows by induction.
