Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently reopened an old high school math textbook and came upon the matrices unit. Some of the questions were those rewrite-in-linear-form problems: given, say, $M^2 = 2M - I$, express in linear form ($aM+bI$) the matrices $M^3$ and $M^4$. The method of solution would be to express $M^n$ as $M^{n-1}M$ and continue expanding each consecutive set of powers until you end up substituting in the original $M^2 = 2M-I$, for answers of $M^3 = 3M-2I$ and $M^4 = 4M-3I$. Further, induction proof problems could also be posed, such as proving that $M^n = nM - (n-1)I$ for all $n \in \mathbb{Z}^+$. (Technically, it could also be for $n \in \mathbb{Z}$ if you consider $M^{-n} \equiv (M^{-1})^n \equiv (M^n)^{-1}$, which is relevant.)

I decided to take this a step further, and see if I could take powers of $M$ where $M^2 = aM + bI$. After some experimentation, one can define two related sequences $(a_n)$ and $(b_n)$ which describe linear form coefficients of $M^n$. Trivially, $M^1 = M = 1M + 0I$ and $M^0 = MM^{-1} = I = 0M + 1I$, which defines $a_0$, $a_1$, $b_0$, and $b_1$ as 0, 1, 1 and 0, respectively.

From this, and by the properties of expanding powers through $M^2 = a_2M + b_2I$, $$\begin{align} &\text{Basic} \\ a_0 &= b_1 = 0 \\ a_1 &= b_0 = 1 \\ \\ &\text{Following} \\ a_{n+1} &= a_2 a_n + b_n \\ b_{n+1} &= b_2 a_n \\ \\ &\text{Preceding} \\ a_{n-1} &= \frac{1}{b_2}b_n \\ b_{n-1} &= a_n - \frac{a_2}{b_2} b_n \\ \end{align}$$ With a little playing around, one finds that $$a_n = a_2 a_{n-1} + b_2 a_{n-2}$$ which looks a little like the Fibonacci sequence, and since $b_n$ is already defined in terms of $a_n$, the crux of the problem lies in a non-recurring equation for $a_n$, given $a_2$ and $b_2$ as parameters.

Is there a formula for $a_n$, and subsequently, $b_n$? Am I on the right track with this method or is there a more elegant exploitability in these sequences?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Nice observation! What you have here are indeed generalized Fibonacci sequences, and they do indeed have closed forms generalizing Binet's formula. Since you're already taking powers of matrices, learn just a little more linear algebra and you'll understand how to do this when those matrices are diagonalizable. It would also be a good idea to learn about the Cayley-Hamilton theorem.

The general statement is a little messy, but in the special case that the polynomial $t^2 = at + b$ has distinct roots $r_1, r_2$, then $$a_n = \frac{r_1^n - r_2^n}{r_1 - r_2}$$

and $b_n$ has a similar expression. The idea is to look at the vector space of sequences $c_n$ satisfying $$c_{n+2} = a c_{n+1} + b c_n.$$

This vector space has dimension $2$ because such a sequence is uniquely determined by $c_0$ and $c_1$, but on the other hand $c_n = r_1^n$ and $c_n = r_2^n$ both clearly lie in it. It follows that these two sequences in fact form a basis of this vector space, so any solution can be expressed as a linear combination of them.

share|improve this answer
add comment

Your Answer

 
discard

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.