Let $Q_k$ be the $k$-hypercube. Assume that $Q_k$ has a Hamiltian cycle for each $k \geq 2$. Assume that $ 4 \leq k$. Show that for each $ 2 \leq p < q < k$, $Q_k$ has a cycle of length $2^p + 2^q$.
I am not sure how to prove this. Please help.
I am thinking of using induction on the number of vertices.
Note: $Q_k$ can be decomposed into 2 copies of hypercubes in lower dimension => $Q_{k-1} Q_{k-1}$.
Note: Hamiltonian cycle is a Hamiltonian path that starts and ends at the same vertex, which visits each vertex exactly once.
Every hypercube is Hamiltonian. (You can prove this easily by induction on the dimension of the hypercube.) Now let $e_1, \ldots, e_k$ be unit coordinate vectors (i.e. $e_i$ has a $1$ in the $i$th coordinate slot and $0$ everywhere else) and consider the disjoint sub-hypercubes $$S_p = \{c_1 e_1 + \ldots + c_p e_p | (\forall 1 \leq i \leq p) c_i \in \{0, 1\} \}$$ and $$S_q = \{c_1 e_1 + \ldots + c_q e_q + e_k | (\forall 1 \leq i \leq q) c_i \in \{0, 1\} \}$$
Take Hamiltonian paths on $S_p$ and $S_q$ such that the path on $S_p$ joins the origin to $e_1$ and such that the path on $S_q$ joins $e_k$ to $e_1 + e_k$. (Once you have one Hamiltonian path on a hypercube, you can rotate it to connect the origin to whichever adjacent vertices you choose.) Then splice the two paths together by severing the connections $0 \to e_1$ in $S_p$ and $e_k \to e_1 + e_k$ in $S_q$ and instead connecting $0 \to e_k$ and $e_1 \to e_1 + e_k$. This gives you the necessary cycle.