# “Non-commutative” Recurrence relation $C_m = \alpha_m C_{m-1} + \beta_m C_{m-2}$

I have a problem, which is probably quite trivial. Consider a recurrence relation of the form

$$C_m = \alpha_m C_{m-1} + \beta_m C_{m-2},$$ where the coefficients $\alpha_m$ and $\beta_m$ are non-commuting. In my problem, the $C_m$'s are functions of certain variables and the coefficients are (slightly complicated) differential operators. Now assuming that $C_{-1} = 0$, I want to obtain a relation of the form $$C_m = P_m(\alpha, \beta)C_0,$$ where $P(\alpha, \beta)$ is a polynomial in $\{\alpha_n\}_{n=1}^{m}$ and $\{\beta_n\}_{n=1}^{m}$. For example for $\beta_n = 0$, it's given by $P_m(\alpha,0) = \prod_{n=0}^{m-1}\alpha_{m-n}= \alpha_m\alpha_{m-1}\dots\alpha_1$. If one iterates the first equation, a certain pattern emerges, but it's not clear how to write down a compact expression for $P_m(\alpha,\beta)$.

I guess there are certain standard tricks for these kind of problems, any suggestions?

-
I think the "standard tricks" are for the commuting case. –  GEdgar Mar 22 '12 at 23:54

Let $N_{\le m}$ be the set of positive integers up to $m$, i.e. $\{1,2,3,\ldots,m\}$. Let $T_m$ comprise all $S \subset N_{\le m-1}$ where you have $s \in S \implies s+1 \not \in S$; $T_m$ is a subset of the powerset of $N_{\le m-1}$. Let $S_{+1}$ be such that $s \in S \iff s+1 \in S_{+1}$. You could define $T_m$ as comprising all $S \subset N_{\le m-1}$ where you have $S \cap S_{+1} = \emptyset.$
Then $$P_m(\alpha,\beta) = \sum_{S \in T_m} \left(\prod_{r \in N_{\le m} \backslash (S \cup S_{+1})} \alpha_r \right) \left(\prod_{s \in S} \beta_s \right)$$
Thanks for your suggestion Henry, I am afraid that this expression is slightly too abstract for my needs. It would be nicer to have $P_m(\alpha,\beta)$ written in terms of concrete sums and products. By the way, your expression doesn't seem to take into account that none of the $\alpha$ and $\beta$'s commute. –  Heidar Mar 26 '12 at 18:53