For $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{n\times m}$ such that $rank[A\hspace{2mm}B]=n$ do we necessarily have $rank[A^k\hspace{2mm}B\hspace{2mm}AB\hspace{2mm}\dots\hspace{2mm}A^{k-1}B]=n$ for all $k\in\mathbb{Z}_{\geq1}$?
After some random matrix generation in MATLAB, I'm pretty sure that it is true. In trying to prove it, I was hoping to be able to take a shortcut by proving that $rank[A\hspace{2mm}B]=n$ implies $rank[A^k\hspace{2mm}B]=n$ or $rank[B\hspace{2mm}AB\hspace{2mm}\dots\hspace{2mm}A^{k-1}B]=n$ but a counterexample to both is given by taking $A= \begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1 \end{bmatrix}$, $B= \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix}$ and $k=2$.
Both hints and outright proofs are welcome.
The claim is true and I'll give a general sketch. If $\mathrm{rank}\begin{bmatrix} A & B \end{bmatrix} = n$ then the image of $\begin{bmatrix} A & B \end{bmatrix}$ is $\mathbb{R}^n.$ It follows that $$\mathrm{im} \begin{bmatrix}A^2 & A B\end{bmatrix} = \mathrm{im}\, A\,\begin{bmatrix} A & B \end{bmatrix}$$ is just the image of $A.$ From this you should be able to conclude that $$ \mathrm{im}\begin{bmatrix} A^2 & B & A B \end{bmatrix} = \mathrm{im}\begin{bmatrix} B & A B & A^2\end{bmatrix} = \mathrm{im}\begin{bmatrix} B & A \end{bmatrix}, $$ which establishes the base case. This fact can then be used to establish the complete statement by making the following observation, $$\begin{aligned} \mathrm{im}\begin{bmatrix} A^k & B & A B & \cdots & A^{k-2} B & A^{k-1} B \end{bmatrix} &= \mathrm{im}\begin{bmatrix} B & A B & \cdots & A^{k-2} B & A^{k-1} B & A^k \end{bmatrix}\\ &= \mathrm{im}\begin{bmatrix} B & A B & \cdots & A^{k-2} B & A^{k-1} \begin{bmatrix} B & A \end{bmatrix} \end{bmatrix} \end{aligned}$$