Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I think the "standard tricks" are for the commuting case. – GEdgar Mar 22 '12 at 23:54
up vote 2 down vote accepted

I don't think there is an easy notation: it might be easier to program.

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)$$

share|cite|improve this answer
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
@Heidar: I can't help on the first point. On the second, you would have to "decommute" the products so the subscripts were decreasing from left to right. – Henry Mar 26 '12 at 21:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.