# Linear system of equations that arises from recurrence relation.

So when solving a third order homogenous recurrence relation I end upp with the task of determening the constants $$a,b$$ and $$c$$. The initial conditions give rise to the following system of equations:

$$\left\{ \begin{array}{rcr} 2a+(1+\sqrt{6})b+(1-\sqrt{6})c & = & 0\\ 4a+(1+\sqrt{6})^2b+(1-\sqrt{6})^2c & = & 0\\ 8a+(1+\sqrt{6})^3b+(1-\sqrt{6})^3c & = & 1 \end{array} \right.$$

I've verified that this system is correct but now I need to solve it. I find brute force Gaussian elimination quite tedious to do (or maybe there is some trick to make it simple?). Is there any other easier method to solve this without having to spend 3-4 pages of hand written scribble?

$$a=-\frac{1}{10}, \ b=\frac{1}{10\sqrt{6}}, \ c=-\frac{1}{10\sqrt{6}}.$$

• It’s the third column of the inverse of the coefficient matrix, but I’m not sure that’s going to be any less work. – amd Feb 17 '19 at 22:13

I would suggest that you use Cramer's method, i.e. using determinants.

One thing that will help you is to notice the following: Let $$\phi=1+\sqrt6$$. Then you have $$1-\sqrt6 = \frac{(1-\sqrt6)(1+\sqrt6)}{1+\sqrt6}=\frac{-5}{\phi}\ \ \ (*)$$ Put this into the equations, get rid of the fractions and find the determinants. One property that will be useful is that if a row or column of a determinant has a common factor, you can take the factor out in front of the determinant. After solving the system you will get expressions that contain $$\phi$$ and you will have to calculate some powers of $$\phi$$ which is not too hard to do.

Edit: More steps.

By using (*), you can eventually get to the system: $$\begin{eqnarray*} 2\phi a+\phi^2 b-5c &=& 0 \\ 4\phi^2 a+\phi^4 b+25c &=& 0 \\ 2\phi^3 a+\phi^6 b-125c &=& \phi^3 \end{eqnarray*}$$

Now, the determinants are: $$D = \left|\begin{array}{ccc} 2\phi & \phi^2 & -5 \\ 4\phi^2 & \phi^4 & 25 \\ 8\phi^3 & \phi^6 & -125 \\ \end{array}\right| = 2\phi\cdot\phi^2\cdot(-5) \left|\begin{array}{ccc} 1 & 1 & 1 \\ 2\phi & \phi^2 & -5 \\ 4\phi^2 & \phi^4 & 25 \\ \end{array}\right|$$ This determinant can be calculated using Sarrus' rule. $$D_a = -5\phi^2 \left|\begin{array}{ccc} 0 & 1 & 1 \\ 0 & \phi^2 & -5 \\ \phi^3 & \phi^4 & 25 \\ \end{array}\right| =-5\phi^5 \left|\begin{array}{cc} 1 & 1 \\ \phi^2 & -5 \\ \end{array}\right|$$ $$D_b = -10\phi \left|\begin{array}{ccc} 1 & 0 & 1 \\ 2\phi & 0 & -5 \\ 4\phi^2 & \phi^3 & 25 \\ \end{array}\right| = 10\phi^4 \left|\begin{array}{cc} 1 & 1 \\ 2\phi & -5 \\ \end{array}\right|$$ $$D_c = 2\phi^3 \left|\begin{array}{ccc} 1 & 1 & 0 \\ 2\phi & \phi^2 & 0 \\ 4\phi^2 & \phi^4 & \phi^3 \\ \end{array}\right| = 2\phi^6 \left|\begin{array}{cc} 1 & 1 \\ 2\phi & \phi^2 \\ \end{array}\right|$$ You should get $$D=-10\phi^4(2\phi^4+\phi^3+5\phi-50)$$ $$D_a = 5\phi^5(\phi^2+5)$$ $$D_b=-10\phi^4(2\phi+5)$$ $$D_c=2\phi^7(\phi-2)$$

The solutions are then $$a=D_a/D$$, $$b=D_b/D$$, $$c=D_c/D$$. Plugging in the numbers I get the same solution that you gave.

Please let me know if I have made any errors along the way.

• I'll edit in my attempt with this method in my answer. – Parseval Feb 17 '19 at 23:00
• @Parseval I have solved it using this method, and the only tedious part is finding the system determinant, but the rest is not that complicated. – Haris Gušić Feb 17 '19 at 23:11
• @Parseval Indeed, but the $D_a,D_b,D_c$ are quite easy if you factor out common factors as I described. – Haris Gušić Feb 17 '19 at 23:18
• @Parseval You can factor out another $\phi^2$ there. I will update my answer with more steps. – Haris Gušić Feb 17 '19 at 23:24
• @Parseval You are very welcome! Keep in mind though that Gaussian elimination can be more convenient in some situations. – Haris Gušić Feb 18 '19 at 0:02

Very basic (done by hand in less than a page with pen and paper).

Consider $$2 a+A b+B c = 0\tag 1$$ $$4 a+A^2 b+B^2 c =0\tag 2$$ $$8 a+A^3 b+B^3 c =1\tag 3$$

Use $$(1)$$ and $$(2)$$ and solve for $$(a,b)$$ to get $$a=\frac{B (B-A)}{2 (A-2)} c\qquad \text{and} \qquad b=\frac{(2-B) B }{(A-2) A}c$$ Plug in $$(3)$$ and solve for $$c$$ to get $$c=\frac{1}{(2-B) B (A-B)}\implies a=\frac{1}{2 (A-2) (B-2)}\qquad \text{and} \qquad b=\frac{1}{(A-2) A (A-B)}$$

Now, make $$A=1+\sqrt 6$$ and $$B=1-\sqrt 6$$.