What is the general formula for these matrix coefficients? Question
I devised an interesting math puzzle for myself but couldn't deduce any solution:
Given:
$$AB=BA=A+B$$
$$ (AB)^n = \sum_{j=1}^n a_j A^j +  b_j B^j$$
It's obvious $a_j=b_j$ but what is the general formula for any given $n$? 
$$a_j=b_j = ?$$
For Example
$$ (AB)^2= A^2 + 2A + 2B + B^2 $$
or:
$$ (AB)^3= A^3 + 3A^2 + 3A + 3B + 3B^2 + B^3$$
 A: There was a mistake in my original answer, so I had to edit it.
Let's first look at the first powers:
\begin{align*}(AB)^1& =A+B \\
(AB)^2& =A^2+2A+2B+B^2 \\
(AB)^3& =A^3+3A^2+6A+6B+3B^2+B^3 \\
(AB)^4& =A^4+4A^3+10A^2+20A+\dots \\
\end{align*}
As the expression is symmetric in $A$ and $B$, we can focus on the coefficients of $A$.
We now compare this to Pascal's triangle

We recognise the coefficients as the various (truncated) diagonals, so there is our induction claim, for $n\ge 1$:
$$(AB)^n=\sum_{k=1}^n{2n-1-k \choose n-k}(A^k+B^k)$$
To prove it we need that $$A^kB=\sum_{l=1}^kA^l+B$$.
If we look at the coefficient of $A^k$ in $A^n$,$1<k\leq n$, we see that due to the above equality, it will be given by the sum of the coefficients of the $A^l$ with $l\ge k-1$, and it will be given by twice the mentioned sum if $k=1$.
But these are the entries of a trucated diagonal inside Pascal's triangle, which starts from the very boundary ($1$). so instead of considering that $1$ in the sum, we can consider the $1$ just below to the left, and then use the usual rule for the Pascal triangle, i.e. that the sum of two side by side numbers is equal to the number in the middle below them, makes computing of this diagonal sum easy. For $k=1$ one can obtain the analogous result by noting that summing up to the $0$'th entry is equivalent to doubling the previous sum. This completes the proof.
A: Let's take a more general approach by evaluating $A^m B^n$.
Let $$A^m B^n=\sum_{i=1}^m {f_{i}(m,n)A^i}+\sum_{j=1}^n {g_{j}(m,n)B^j}$$
It can be seen that $f_{1}(1,n)=g_{i}(1,n)=1$ for $1\le i\le n$
By considering $A^{m+1}B^n$, one can show that: $$f_{1}(m+1,n)=\sum_{i=1}^n {g_{i}(m,n)}$$ 
$$g_{i}( m+1,n)=\sum_{j=i}^n {g_{j}(m,n)}$$
Also notice that $f_{i}(m,n)=f_{1}(m-i+1,n)$
Then by induction, $$f_{i}(m,n)=\binom{m+n-i-1}{m-i}, g_{i}(m,n)=\binom{m+n-i-1}{m-1}.$$
The answer can then be deduced by setting $m=n$.
