To find the close form for the last value of a matrix product Suppose I have two matrices
$$A = \begin{bmatrix} 0 & 1 \\ a_2 & a_1\end{bmatrix}$$
$$B = \begin{bmatrix} 0 & 1 \end{bmatrix}$$
Then $AB^T = \begin{bmatrix} 1 \\ a_1\end{bmatrix}$, the last term is $a_1$
Now I expand matrix $A$ and $B$ a little bit to get 
$$A = \begin{bmatrix} 0 & 1 & 0  \\ 0 & 0 & 1 \\ a_3 & a_2 & a_1\end{bmatrix}$$
$$B = \begin{bmatrix} 0 & 0 & 1 \end{bmatrix}$$
Then I find $AB^T = \begin{bmatrix} 0 \\ 1 \\ a_1\end{bmatrix}$, the last term is $a_1$, furthermore 
 $A^2B^T = \begin{bmatrix} 1 \\ a_1 \\ a_1^2 + a_2 \end{bmatrix}$, the last term is $a_1^2 + a_2$, neato!
Finally let's define our matrix to be:
$$A = \begin{bmatrix} 0 & 1 & 0 & 0  \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ a_4 & a_3 & a_2 & a_1\end{bmatrix}$$
$$B = \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix}$$
As before, I find $AB^T = \begin{bmatrix} 0 \\ 0 \\ 1 \\ a_1\end{bmatrix}$, the last term is $a_1$, furthermore 
 $A^2B^T = \begin{bmatrix} 0 \\ 1 \\ a_1 \\ a_1^2 + a_2 \end{bmatrix}$, the last term is $a_1^2 + a_2$
Curiously, I can compute $A^3B^T$ and obtain $\begin{bmatrix} 1 \\ a_1 \\ a_1^2 + a_2 \\ a_3 + a_2a_1 + a_1(a_1^2+a_2) \end{bmatrix}$
Now suppose A and B are both N dimensional matrices.
Is there a closed form solution for the n by nth value of the product $A^{n-1}B^T$? 
Note: $A$ and $B$ pair are what known as the canonical controllable form
 A: Let $(A^{n-1})_{n\times n}\times (B^T)_{n\times 1}=C_{n\times 1}$  $\qquad \qquad (C=[c_1 \ldots c_n]^T)$
The set $C$ can be defined recursively as follows:
\begin{align}
c_1&=1 \\
c_k&=\sum_{i=1}^{k-1}a_ic_{k-i} \qquad (2\leq k \leq n)\end{align}
To see why, first note that since all elements of $B$ except the last one are $0$, only the last column of $A^{n-1}$ takes part in forming $C$. So we need to focus on how this column evolves starting at $A^1$.
Also notice the special structure of $A$. Informally speaking, when a matrix of this kind is multiplied by another matrix $D$, it "pushes" the rows of $D$ one level up: (The last row is hidden to illustrate the point more clearly)
$$
\begin{bmatrix}
0&1&0&0\\
0&0&1&0\\
0&0&0&1\\
\alpha&\beta&\gamma&\delta
\end{bmatrix}
\begin{bmatrix}
a&b&c&d\\
e&f&g&h\\
i&j&k&l\\
m&n&o&p
\end{bmatrix}
=
\begin{bmatrix}
e&f&g&h\\
i&j&k&l\\
m&n&o&p\\
& & &
\end{bmatrix}
$$
$$
\Bigg(\begin{bmatrix}
0&1&0&0\\
0&0&1&0\\
0&0&0&1\\
\alpha&\beta&\gamma&\delta
\end{bmatrix}\Bigg)^2
\begin{bmatrix}
a&b&c&d\\
e&f&g&h\\
i&j&k&l\\
m&n&o&p
\end{bmatrix}
=
\begin{bmatrix}
i&j&k&l\\
m&n&o&p\\
& & &\\
&&&
\end{bmatrix}
$$
It follows from these two observation that we just need to find out how the last element of the last column of $A$ evolves. Now it should be straightforward to see why $C$ is defined by the recursive definition mentioned above. You should be able to construct the formal proof (if it is necessary), though it is tedious and takes time.
A: It's more helpful to write $\begin{bmatrix} 1 \\ a_1 \\ a_2 + a_1^2 \\ a_3 + 2 a_1a_2 + a_1^3 \end{bmatrix}$.
The next one is $\begin{bmatrix} 1 \\ a_1 \\ a_2 + a_1^2 \\ a_3 + 2 a_1a_2 + a_1^3\\a_4+2a_1a_3+3 a_1^2a_2 +a_2^2+a_1^4 \end{bmatrix}$.
The next one is $\begin{bmatrix} 1 \\ a_1 \\ a_2 + a_1^2 \\ a_3 + 2 a_1a_2 + a_1^3\\a_4+2a_1a_3+3 a_1^2a_2 +a_2^2+a_1^4\\a_5+2a_1a_4+2a_2a_3+3 a_1a_2^2+3a_3a_1^2 +4a_1^3a_2+a_1^5 \end{bmatrix}$.
Each term is linked to a partition of n.
So for example, one of the partitions of 5 is 2+2+1. Therefore one of the terms is the product of $a_2$ and $a_2$ and $a_1$, which is $a_1a_2^2$.
Each term has a coefficient that is equal to the number of $a_i$ that are multiplied together to make that term.
So for example the term above is the product of three values $a_2$ and $a_2$ and $a_1$, so the coefficient is 3.
The only exception to this coefficient rule is the last term, which is always $a_1^n$. 
Partitions of 6 are:
6: $a_6$
1+5: $2a_1a_5$
2+4: $2a_2a_4$
3+3: $2a_3^2$
1+1+4: $3a_1^2a_4$
1+2+3: $3a_1a_2a_3$
2+2+2: $3a_2^3$
1+1+1+3: $4a_1^3a_3$
1+1+2+2: $4a_1^2a_2^2$
1+1+1+1+2: $5a_1^4a_2$
1+1+1+1+1+1: $a_1^6$
