The root condition is equivalent to bounded powers of the multistep companion matrix

The companion matrix has characteristic polynomial $\rho \mathrm{/}{\alpha }_k$ by [F2]. By [F4] and [F5], write $C=SJ{S}^{-1}$ over $\mathbb{C}$, where $J$ is a block diagonal sum of Jordan blocks. Each block $J_m(\lambda )$ contributes $(z-\lambda {)}^m$ to the characteristic polynomial by [F6] and [F7]. Thus the algebraic multiplicity of each root of $\rho$ is the sum of the sizes of its Jordan blocks.

If $\rho$ has a root $\lambda$ with $\mathrm{\mid }\lambda \mathrm{\mid }>1$, the complex sequence $u_n={\lambda }^n$ solves the homogeneous recurrence. If $\lambda$ is real, this is an unbounded real solution. If $\lambda$ is nonreal, its real and imaginary parts solve the real recurrence because the coefficients are real, and $\max (\mathrm{\mid }\mathrm{Re}{u}_n\mathrm{\mid },\mathrm{\mid }\mathrm{Im}{u}_n\mathrm{\mid })\ge \mathrm{\mid }{u}_n\mathrm{\mid }\mathrm{/}\sqrt{2}$ for every $n$; hence at least one of those real solutions is unbounded along a subsequence. By [F3], the corresponding real solution has an initial state whose companion iterates are unbounded.

If a root $\lambda$ of modulus one has multiplicity $m\ge 2$, write $\rho (z)=(z-\lambda {)}^{m}q(z)$. For the forward shift $E{u}_n=u_{n+1}$, $(E-\lambda )(n^s{\lambda }^n)={\lambda }^{n+1}((n+1{)}^s-n^s)$, whose polynomial factor has degree $s-1$. Iterating $m$ times gives $(E-\lambda {)}^{m}u=0$ for $u_n=n^{m-1}{\lambda }^n$; since $q(E)$ commutes with $(E-\lambda {)}^m$, this sequence satisfies $\rho (E)u=0$, yet $\mathrm{\mid }{u}_n\mathrm{\mid }=n^{m-1}$ is unbounded. If coefficients are real and $\lambda$ is nonreal, the real and imaginary parts are real recurrence solutions and at least one is unbounded along a subsequence.

Suppose the root condition holds. If $\mathrm{\mid }\lambda \mathrm{\mid }=1$, its algebraic multiplicity is one by [F1], so its only Jordan block has size one.

For a block with $0<\mathrm{\mid }\lambda \mathrm{\mid }<1$, the binomial identity gives $J_m(\lambda {)}^n={\sum }_{j=0}^{m-1}\left(\genfrac{}{}{0px}{}{n}{j}\right){\lambda }^{n-j}{N}^j$. For each fixed $j$, the ratio of successive terms $n^j\mathrm{\mid }\lambda {\mathrm{\mid }}^{n-j}$ tends to $\mathrm{\mid }\lambda \mathrm{\mid }<1$, so this scalar sequence is bounded; if $\lambda =0$, the block powers vanish for $n\ge m$. A unit-modulus block has size one by step 2.1 and therefore has powers of modulus one. Finitely many blocks give ${\sup }_n\mathrm{\parallel }{J}^n{\mathrm{\parallel }}_{\mathrm{\infty }}<\mathrm{\infty }$.

For any matrices $A,B$, expanding entries and applying the triangle inequality gives $\mathrm{\parallel }AB{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{\parallel }B{\mathrm{\parallel }}_{\mathrm{\infty }}$. Hence $\mathrm{\parallel }{C}^n{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }S{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{\parallel }{J}^n{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{\parallel }{S}^{-1}{\mathrm{\parallel }}_{\mathrm{\infty }}$, uniformly in $n$.

Under the root condition, steps 2.1, 3.1, and 4.1 bound the powers of $C$. If it fails, steps 1.2–1.3 give an unbounded homogeneous mode, and [F3] turns that mode into an initial state with unbounded companion iterates. Thus the powers are bounded exactly under the root condition, and [F1] gives the equivalent zero-stability statement.