-3

How to solve these kind of recurrence relations using matrices:

$$A_{n+1} = \sqrt 2 (A_n + B_n) - \sqrt 3 (A_n - B_n)$$ $$B_{n+1} = \sqrt 2 (A_n - B_n) + \sqrt 3 (A_n + B_n)$$

with initial $A_0$ and $B_0$ given.

I want a general idea about how to make the matrix which can be used to solve these kind of recurrence relations.

Thanks.

bewithaman
  • 101

1 Answers1

3

Let $$M=\begin{pmatrix} \sqrt2-\sqrt3&\sqrt2+\sqrt3\\ \sqrt2+\sqrt3&-\sqrt2+\sqrt3 \end{pmatrix}$$

Then $$\begin{pmatrix}A_n\\ B_n\end{pmatrix} = M^n \begin{pmatrix}A_0\\B_0\end{pmatrix}$$

So you need to compute $M^n$ quickly. This can be done by repeated squaring. Note that $\mathrm{tr} M=0$ and $\det M = -(\sqrt{3}-\sqrt2)^2-(\sqrt3+\sqrt2)^2 = -10$. So $M^2-10I=0$, which greatly helps you calculate powers of $M$.

Thomas Andrews
  • 177,126
  • Can I calculate A_0 and B_0 if I am given An and Bn and n? – bewithaman Sep 07 '15 at 01:23
  • If you compute the inverse of $M$, yes, and note that if $N$ is the inverse then $N^2=\frac{1}{10}I$. So you just need to compute $N^n$ with that knowledge. Note that it is essentially $N^{2k}=\frac{1}{10^k}I$ and $N^{2k+1}=N^{2k+2}M=\frac{1}{10^{k+1}}M$. Basically, $M^2=10I$ means $M^{-1}=\frac{1}{10}M$. – Thomas Andrews Sep 07 '15 at 01:27
  • Thanks @ThomasAndrews for the help. – bewithaman Sep 07 '15 at 01:31
  • Do remember that we're dealing with series, not continuous functions. But yeah, for whole numbers, this will give you the right answers. – Daniel Sep 07 '15 at 01:52
  • Clarify your point, @Daniel. Who is suggesting that this is a continuous function? It is not a "series," either, but a sequence. – Thomas Andrews Sep 07 '15 at 01:54
  • Ah, sorry -- I misspoke, it's a sequence, yes. I just wanted to clarify, in case it looked like a function to anybody in this response. I guess my comment wasn't particularly important, just felt like adding something. – Daniel Sep 07 '15 at 18:25
  • @ThomasAndrews Sorry for late reply. I want to learn how to solve recurrence relation using matrices. If you can you share any good article or link which can help me understand the basic concept behind it, I will be very thankful. – bewithaman Sep 11 '15 at 04:40