0.1 Recurrence Relation
Another very popular type of problems in math olympiads and competition in general is recurrence relation. This section discusses different forms of recurrence relation and related problems. One more thing before we get started is that this section is largely based on a series of YouTube videos from WinnersKMO [Win26].
As you probably know, recurrence relation focuses on \(n^\text {th}\) term given its relation with preceding \(k^\text {th}\) terms. One very famous example would be Fibonacci sequence whose terms are defined as \(F_n = F_{n-1} + F_{n-2}\) where \(F_0 = F_1 = 1\). The problems are relatively easy in my opinion until it gets incredibly hard, so let’s get started with some easy cases.
I. \(\mathbf {a_n = a_{n-1} + f(n)}\)
This default type has an effective way of solving because it always gets down to a single formula, which becomes quite evident when we telescope. Consider the following equations. \begin{align*} a_n - a_{n-1} &= f(n) \\ a_{n-1} - a_{n-2} &= f(n-1) \\ &\vdots \\ a_2 - a_1 &= f(2) \end{align*}
Adding the equations, the left-hand side telescopes and we obtain \(a_n - a_1 = \sum _{k=2}^n f(k)\).
Given a recurrence relation \(a_n = a_{n-1} + f(n)\), each term can be represented with the following formula. \[ a_n = \sum _{k=1}^n f(k) + a_1 - f(1) \]
There will be lots of formulas from now, but I honestly think there is no need to memorize them because if we just remember the idea to get to the formulas, then we can solve the problems. Here is an example problem before we move on to the next case.
Exercise 0.1.1: Enoch’s Problem
Let \(a_1, \ldots , a_k\) be a sequence such that \(a_n = a_{n-1} + n^2 - 2n + 1\) for \(n > 1\) and \(a_1 = 2\). Find \(a_{101}\).
Solution.
This sequence has the form \(a_n = a_{n-1} + f(n)\) where \(f(n) = n^2 - 2n + 1\). Telescoping, we obtain the following equations. \begin{align*} a_{101} &= \sum _{k=1}^{101} (k-1)^2 + 2 - 1 = \sum _{n=0}^{100} n^2 + 1 \\ &= \frac {100(100 + 1)(200 + 1)}{6} + 1 = 338351 \end{align*}
Therefore, \(a_{101} = 338351\).
Continuing with the first form, here is the second one.
II. \(\mathbf {a_n = a_{n-1} f(n)}\)
This case is also very popular and can be solved using the same method as before. \begin{align*} \frac {a_n}{a_{n-1}} &= f(n) \\ \frac {a_{n-1}}{a_{n-2}} &= f(n-1) \\ &\vdots \\ \frac {a_2}{a_1} &= f(2) \end{align*}
Telescoping, we obtain \(\frac {a_n}{a_1} = \prod _{k=2}^n f(k)\).
The terms in a recurrence relation \(a_n = a_{n-1} f(n)\) can be represented with the following formula. \[ a_n = a_1 \prod _{k=2}^n f(k) \]
Here is another problem derived from the previous one.
Exercise 0.1.2: Enoch’s Problem
Let \(a_1, \ldots , a_k\) be a sequence such that \(a_n = a_{n-1} ( n^2 - 2n + 1)\) for \(n > 1\) and \(a_1 = 1\). Find \(a_{101}\).
Solution.
Notice that this sequence has the form \(a_n = a_{n-1} f(n)\) where \(f(n) = (n-1)^2\). Telescoping, we obtain the following equations. \[ a_{101} = \prod _{k=2}^{101} (k-1)^2 = \prod _{n=1}^{100} n^2 = (100!)^2 \] Therefore, \(a_{101} = (100!)^2\).
The first two cases were relatively simple. Continuing, we can continue with their variations.
III. \(\mathbf {a_n = p a_{n-1} + q}\)
From this case, there are many different ways to get an answer. Let’s start with my personal favorite one.
Solution I.
The first method is to directly substitute. \begin{align*} a_n &= p a_{n-1} + q \\ &= p (p a_{n-2} + q) + q = p^2 a_{n-2} + (p + 1)q \\ &= p^2 (p a_{n-3} + q) + (p + 1)q = p^3 a_{n-3} + (p^2 + p + 1)q \\ &\qquad \quad \vdots \\ &= p^{n-1} a_1 + q \sum _{k=0}^{n-2} p^k \end{align*}
Rearranging the equation, we obtain the following equation. \[ a_n = p^{n-1} a_1 + \frac {1 - p^{n-1}}{1 - p} \cdot q \] I personally like this method because it feels intuitive and quite natural to just substitute. The second method is slightly less intuitive, but it should be faster and better if you prone to make arithmetic mistakes.
Solution II.
This method will convert the form of this recursive equation. First, assume that there exists an \(\alpha \) such that the following equation holds. \[ a_n - \alpha = p (a_{n-1} - \alpha ) \] If there exists such alpha, then it is evident that we can telescope to obtain the following equation. \[ a_n - \alpha = p^{n-1} (a_1 - \alpha ) \] This is much easier to work with compared to our initial equation.
From the equation \(a_n - \alpha = p (a_{n-1} - \alpha )\), we can notice that \(p a_{n-1} + q - \alpha = p (a_{n-1} - \alpha )\) and \(q = \alpha (1 - p)\). In other words, \(\alpha = \frac {q}{1 - p}\). This shows that \(\alpha \) always exists given that \(p \neq 1\). In other words, whenever we see this case, we can let \(\alpha = \frac {q}{1 - p}\) and use \(a_n - \alpha = p^{n-1} (a_1 - \alpha )\). Substituting, \begin{align*} a_n &= p^{n-1} a_1 + \alpha \left ( 1 - p^{n-1} \right ) = p^{n-1} a_1 + \frac {q}{1 - p} \left ( 1 - p^{n-1} \right ) \\ &= p^{n-1} a_1 + q \sum _{k=0}^{n-2} p^k = p^{n-1} a_1 + \frac {1 - p^{n-1}}{1 - p} \cdot q \end{align*}
is obtained and this result is consistent.
Before moving on to the next case, here is an example problem.
Exercise 0.1.3: Enoch’s Problem
Find \(a_{101}\) if \(a_n = 2a_{n-1} + 3\) for \(n > 1\) and \(a_1 = 2\).
Solution.
First, we can try substituting \(a_{n-1}\) in the given equation in terms of \(a_{n-2}\) and continue the process until we reach \(a_1\). \begin{align*} a_{101} &= 2 a_{100} + 3 \\ &= 2 (2 a_{99} + 3) + 3 = 2^2 a_{99} + (2 + 1) 3 \\ &\qquad \quad \vdots \\ &= 2^{100} a_1 + 3 \sum _{k=0}^{99} 2^k \end{align*}
Therefore, \(a_{101} = 2^{101} + \frac {1 - 2^{100}}{1 - 2} \cdot 3 = 2^{101} - 3 + 3 \cdot 2^{100} = 2^{100} 5 - 3\).
Continuing from this case, we have its extension where \(q\) is not a constant but a function.
IV. \(\mathbf {a_n = k a_{n-1} + f(n)}\)
This problem too can be solved with very similar methods from the previous, its just a little more unkind. Let’s start with my favorite method.
Solution I.
In this solution, we will define a new term \(b_n = \frac {a_n}{k^n}\). Consider the following equations. \begin{align*} \frac {a_n}{k^n} &= \frac {a_{n-1}}{k^{n-1}} + \frac {f(n)}{k^n} \\ b_n &= b_{n-1} + \frac {f(n)}{k^n} = b_{n-1} + g(n) \end{align*}
This is the same as Case I and telescoping gives us \[ b_n = \sum _{k=1}^n g(k) + b_1 - g(1) \] and rewriting this, we obtain the following. \[ \frac {a_n}{k^n} = \sum _{l=1}^n \frac {f(l)}{k^l} + \frac {a_1}{k} - \frac {f(1)}{k} = \sum _{l=1}^n \frac {f(l)}{k^l} + \frac {a_1 - f(1)}{k} \] This method simply defines a new sequence to represent it into an easier problem.
Solution II.
The second method is very similar to the second solution for Case III. First, we will assume that there exists a function \(F(n)\) such that the following equation holds. \[ a_n - F(n) = k(a_{n-1} - F(n-1)) \] Rewriting this, we can see that \(a_n = k^{n-1} (a_1 - F(1)) + F(n)\). From here it depends on the problem, but it shouldn’t be too difficult because we only need to find \(F(n)\).
Before moving on to the next case, here is a practice problem.
Exercise 0.1.4: Enoch’s Problem
Find \(a_n\) in terms of \(n\) if \(a_n = 3a_{n-1} - 2n + 1\) and \(a_1 = 2\).
Solution.
First, we can try to divide both sides by \(3^n\) and let \(b_n = \frac {a_n}{3^n}\). \begin{align*} \frac {a_n}{3^n} &= \frac {a_{n-1}}{3^{n-1}} - \frac {2n - 1}{3^n} \\ b_n &= b_{n-1} - \frac {2n - 1}{3^n} \end{align*}
Telescoping we obtain \(b_n - b_1 = -\sum _{k=2}^n \frac {2k - 1}{3^k}\). Let \(S = \sum _{k=2}^n \frac {2k - 1}{3^k}\) and consider the following equations for index-shifting. \begin{align*} S &= \sum _{k=2}^n \frac {2k - 1}{3^k} \\ \frac {S}{3} &= \sum _{k=2}^n \frac {2k - 1}{3^{k+1}} = \sum _{j=3}^{n+1} \frac {2j - 3}{3^j} \\ \frac {2}{3} S &= \sum _{k=2}^n \frac {2k - 1}{3^k} - \left ( \sum _{j=2}^n \frac {2j - 3}{3^j} - \frac {1}{9} + \frac {2n - 1}{3^{n+1}} \right ) \\ &= \sum _{k=2}^n \frac {2}{3^k} + \frac {1}{9} - \frac {2n - 1}{3^{n+1}} \end{align*}
Therefore, \(S = \sum _{k=2}^n \frac {1}{3^{k-1}} + \frac {1}{6} - \frac {2n - 1}{2 \cdot 3^n} = \frac {1}{3} \cdot \frac { 1 - \frac {1}{3^{n-1}} }{ 1 - \frac {1}{3} } + \frac {1}{6} - \frac {2n - 1}{2 \cdot 3^n}\). Substituting, \begin{align*} \frac {a_n}{3^n} - \frac {2}{3} &= -\left ( \frac {1}{2} - \frac {1}{2 \cdot 3^{n-1}} + \frac {1}{6} - \frac {2n - 1}{2 \cdot 3^n} \right ) \\ \frac {a_n}{3^n} &= -\frac {1}{2} + \frac {1}{2 \cdot 3^{n-1}} - \frac {1}{6} + \frac {2n - 1}{2 \cdot 3^n} + \frac {2}{3} \\ &= \frac {1}{2 \cdot 3^{n-1}} + \frac {2n - 1}{2 \cdot 3^n} = \frac {1}{2 \cdot 3^{n-1}} + \frac {n}{3^n} - \frac {1}{2 \cdot 3^n} \end{align*}
Therefore, \(a_n = n + 1\).
Continuing from this case, here is the next one. From this case the problems could get more complicated, but I don’t think they are necessarily harder because they build from the four cases that we discussed so far.
V. \(\mathbf {a_n = \frac {p a_{n-1}}{q a_{n-1} + r}}\)
This type of problem is relatively simple. To solve them, we can first take the reciprocal of both sides to obtain a more simple problem. \[ \frac {1}{a_n} = \frac {q a_{n-1} + r}{p a_{n-1}} = \frac {q}{p} + \frac {r}{p a_{n-1}} \] Now substituting \(b_n = \frac {1}{a_n}\), we obtain Case III! The next case is a little more complex, but is also quite common.
VI. \(\mathbf {p a_{n+1} + q a_n + r a_{n-1} = 0}\)
For this case, we can separate the cases into two cases. If the problem maker was kind, we could sometimes get \(p + q + r = 0\). In that case, we can simply substitute \(q = -p - r\) to obtain the following equation. \[ p (a_{n+1} - a_n) = r (a_n - a_{n-1}) \] Letting \(b_n = a_n - a_{n-1}\), it is now trivial.
If the problem is not nice enough, which is the most likely case, we will get \(p + q + r \neq 0\). This now becomes quite complicated. For this case, we can try dividing both sides by \(p\). Notice that because \(\frac {q}{p}\) and \(\frac {r}{p}\) are constants, we can always find \(\alpha \) and \(\beta \) such that the following equation holds with Vieta’s formula. \[ a_{n+1} - (\alpha + \beta ) a_n + \alpha \beta a_{n-1} = 0 \] From here, we can again split the equation into two cases depending on the values of \(\alpha \) and \(\beta \).
The first case is when \(\alpha \neq \beta \). Rearranging the equation, we obtain the two distinct equations. \begin{align*} a_{n+1} - \alpha a_n &= \beta (a_n - \alpha a_{n-1}) \\ a_{n+1} - \beta a_n &= \alpha (a_n - \beta a_{n-1}) \end{align*}
Because the equations from a geometric sequence, we can telescope to obtain the following. \begin{align*} a_n - \alpha a_{n-1} &= \beta ^{n-1} (a_2 - \alpha a_1) \\ a_n - \beta a_{n-1} &= \alpha ^{n-1} (a_2 - \beta a_1) \\ \therefore a_{n-1} = \frac {1}{\beta - \alpha } ( \beta ^{n-1} &(a_2 - \alpha a_1) - \alpha ^{n-1} (a_2 - \beta a_1) ) \end{align*}
From here it is not difficult to notice that \(a_n = \frac {1}{\beta - \alpha } (\beta ^n (a_2 - \alpha a_1) - \alpha ^n (a_2 - \beta a_1))\) and it won’t be too difficult to find \(a_1\) and \(a_2\) because they are usually given by the problem.
The second case is when \(\alpha = \beta \). This case is actually nicer because we can simply substitute the values to obtain the following. \begin{align*} a_{n+1} - 2\alpha a_n + \alpha ^2 a_{n-1} &= 0 \\ a_{n+1} - \alpha a_n &= \alpha (a_n - \alpha a_{n-1}) \end{align*}
Again, because this is a geometric sequence, we can telescope to obtain the following equation. \[ a_{n+1} - \alpha a_n = \alpha ^{n-1} (\alpha _2 - \alpha a_1) \] Continuing, we can divided both sides by \(\alpha ^{n+1}\) to telescope again and obtain the following. \begin{align*} \frac {a_{n+1}}{\alpha ^{n+1}} - \frac {a_n}{\alpha ^n} &= \frac {a_2 - \alpha a_1}{\alpha ^2} \\ \therefore \frac {a_n}{\alpha ^n} &= \frac {a_2 - \alpha a_1}{\alpha ^2} \cdot (n - 1) + \frac {a_1}{\alpha } \end{align*}
Therefore, \(a_n = \alpha ^{n-2} (n-1) (a_2 - \alpha a_1) + \alpha ^{n-1} a_1\).
The extended version of this would be when we have more than three variables like the following. \[ p_0 a_n + p_1 a_{n-1} + \cdots + p_{k} a_{n-k} = 0 \] In this case, assume that \(a_n = r^n\) and solve the characteristic equation. If the roots \(r_1, \cdots , r_k\) are all distinct, the solution would be \(a_n = C_1 r_1^n + C_2 r_2^n + \cdots C_k r_k^n\). If any of the roots repeat, make them distinct by multiplying \(n\). For example, if \(r_i\) repeats three times, we can make the roots into \(k\) distinct ones by having the \(k-3\) roots and \(r_i, n r_i, n^2 r_i\). The coefficients \(C_i\) should be easy to find by substitution because initial conditions are most likely evident from the problem.
There are few more cases left, and let’s continue with Case VII.
VII. \(\mathbf {a_n = p a_{n-1} + q b_{n-1}, b_n = r a_{n-1} + s b_{n-1}}\)
This is the case when we are introduced two independent variables. Intuitively, we should eliminate one variable to turn the equations into more simple forms discussed earlier and substitute back into one of the equations to obtain the other. Here is an example.
Exercise 0.1.5: Enoch’s Problem
Given \(a_n = 8a_{n-1} + 7b_{n-1}\) and \(b_n = 2a_{n-1} + 3b_{n-1}\) with \(a_1 = 5\) and \(b_1 = 4\), find \(a_n\) and \(b_n\) in terms of \(n\).
Solution.
For this problem, we could technically use linear algebra, but I think that kinda ruins the fun and elegance of the solution, so let’s not use matrices. Instead, we could try eliminating \(b_n\). Consider the following equations. \begin{align*} 7b_n &= a_{n+1} - 8a_n \\ 7b_n &= 14 a_{n-1} + 21 b_{n-1} = 14 a_{n-1} + 3a_n - 24a_{n-1} \\ \therefore a_{n+1} - 8a_n &= 14 a_{n-1} + 3a_n - 24a_{n-1} \end{align*}
Rewriting the equation, we obtain \(a_{n+1} - 11a_n + 10 a_{n-1} = 0\). This is the previous case, but simpler! Let \(S_n = a_{n+1} - a_n\). Substituting, we obtain \(S_n = 10 S_{n-1}\) and telescoping gives \(S_n = 10^{n-1} S_1\). Moreover, because \(S_1 = a_2 - a_1 = 40 + 28 - 5 = 63\), \(a_{n+1} - a_n = 63 \cdot 10^{n-1}\). Telescoping again, we obtain \[ a_n - a_1 = 63 \sum _{k=2}^n 10^{n-2} = 63 \cdot \left ( \frac {10^{n-1} - 1}{10 - 1} \right ) = 7 (10^{n-1} - 1) \] and \(a_n = 7 \cdot 10^{n-1} - 2\). Substituting to the first equation, \begin{align*} 7b_{n-1} &= a_n - 8a_{n-1} = 7 \cdot 10^{n-1} - 2 - 56 \cdot 10^{n-2} + 16 \\ &= 14 \cdot 10^{n-2} + 14 \end{align*}
holds and \(b_n = 2 \cdot 10^{n-1} + 2\).
This case was easier than the others! Continuing, here is Case VIII.
VIII. \(\mathbf {a_n = \frac {p a_{n-1} + q}{r a_{n-1} + s}}\)
This is another case where we are introduced a fraction. But unlike Case V, you can notice that finding the reciprocal of both sides does not solve the problem. For this case, clever substitution and introducing a new sequence is the key to a solution. Here is an example to demonstrate it.
Exercise 0.1.6: WinnersKMO
Given \(a_1\) and \(a_n = \frac {a_{n-1} + 2}{2a_{n-1} + 1}\), find \(a_n\) [Win26].
Solution.
To solve this problem, let’s first simplify the numerator. \begin{align*} a_n &= \frac { \frac {1}{2} (2a_{n-1} + 1) + \frac {3}{2} }{2a_{n-1} + 1} = \frac {1}{2} + \frac {\frac {3}{2}}{2a_{n-1} + 1} \\ 2a_n - 1 &= \frac {3}{2a_{n-1} + 1} \end{align*}
Let \(b_n = 2a_n + 1\). Substituting, we obtain \(b_n - 2 = \frac {3}{b_{n-1}}\). Here is when we introduce new terms \(c_n\). Let \(b_n = \frac {c_{n+1}}{c_n}\) where \(c_1 = 1\) and \(c_2 = 5\). Substituting, \[ \frac {c_{n+1}}{c_n} - 2 = \frac {3c_{n-1}}{c_n} \] and we obtain \(c_{n+1} - 2c_n - 3c_{n-1} = 0\), and this is Case VI.
This case is not too good but not too bad because solving the characteristic equation is clean. Solving \(x^2 - 2x - 3 = 0\), we get \(x = 3\) and \(x = -1\). Therefore, \(c_n = A3^n + B(-1)^n\). Because \(c_1 = 3A - B\), \(c_2 = 9A + B\), and \(b_1 = 5\), we can see that \(\frac {9A + B}{3A - B} = 5\) and \(6B = 6A\). Because \(c_1 = 1\), \(A = B = \frac {1}{2}\) and \(c_n = \frac {3^n + (-1)^n}{2}\). Now we are done!
Substituting back to \(b_n\), we obtain \[ b_n = \frac { \frac {3^{n+1} + (-1)^{n+1}}{2} }{ \frac {3^n + (-1)^n}{2} } = \frac {3^{n+1} + (-1)^{n+1}}{3^n + (-1)^n} \] and substituting it back to \(a_n\) gives us the following. \[ a_n = \frac {b_n - 1}{2} = \frac { \frac {3^{n+1} + (-1)^{n+1}}{3^n + (-1)^n} - 1 }{2} = \frac { \frac {3^{n+1} + (-1)^{n+1} - 3^n - (-1)^n}{3^n + (-1)^n} }{2} \] Therefore \(a_n = \frac {3^n - (-1)^n}{3^n + (-1)^n}\).
Continuing with this case, here is the final case for this note!
IX. Trigonometry in Recursion
I personally think this case is the hardest to see and apply because for some reason I just can’t remember trigonometric properties properly. But fortunately, I think just some basic relations like double angle, half angle, and sine and cosine relationship are enough. However, the problem is that I think it is very difficult to see when to use trig for recursion. Here is an example from WinnersKMO [Win26] that I enjoyed.
Exercise 0.1.7: WinnersKMO
Given \(a_1 > 0\) and \(a_n = \sqrt {2 + a_{n-1}}\), find \(a_n\) [Win26].
Solution.
One interesting thing that we can notice from this question unlike the other problems is that we don’t have our initial value set. To be honest, I don’t think there is a better way to understand the solution presented here than memorizing patterns, so here we go.
First, recall that \(\cos ^2 \frac {\theta }{2} = \frac {1 + \cos \theta }{2} = \frac {2 + 2\cos \theta }{4}\). Rearranging, we can see that the given equation resembles with the rearrangement \(2\cos \theta = \sqrt {2 + 2\cos 2\theta }\). Following the pattern, let \(a_n = 2\cos \theta _n\) where \(\theta _n = \frac {1}{2} \theta _{n-1}\). Telescoping, we see that \(\theta _n = \frac {1}{2^{n-1}} \theta _1\) and \(a_n = 2 \cos \frac {\theta _1}{2^{n-1}}\). Substituting \(a_1 = 2\cos \theta _1\), we obtain the following equation for \(a_1 \leq 2\). \[ a_n = 2\cos \left ( \frac { \cos ^{-1} \left ( \frac {a_1}{2} \right ) }{2^{n-1}} \right ) \] Now that we have observed the case when \(0 < a_1 \leq 2\), we now need to consider \(a_1 > 2\).
For \(a_1 > 2\), let \(a_1 = \frac {2}{\sin 2\alpha }\). Recall that \(\sin 2\alpha = 2\sin \alpha \cos \alpha \). Substituting, we get the following equations. \begin{align*} a_2 &= \sqrt {2 + \frac {2}{\sin 2\alpha }} = \sqrt {2 + \frac {1}{\sin \alpha \cos \alpha }} = \frac {\sin \alpha + \cos \alpha }{\sqrt {\sin \alpha \cos \alpha }} \\ a_3 &= \sqrt {2 + \frac {\sin \alpha + \cos \alpha }{\sqrt {\sin \alpha \cos \alpha }} } = \frac { \sqrt {\sin \alpha } + \sqrt {\cos \alpha } }{(\sin \alpha \cos \alpha )^\frac {1}{4}} \end{align*}
Repeating, we can see that \begin{align*} a_n &= \frac { (\sin \alpha )^\frac {1}{2^{n-2}} + (\cos \alpha )^\frac {1}{2^{n-2}} }{ (\sin \alpha \cos \alpha )^\frac {1}{2^{n-1}} } = \frac { (\sin \alpha )^p + (\cos \alpha )^p }{ (\sin \alpha \cos \alpha )^\frac {p}{2} } \\ &= (\tan \alpha )^\frac {p}{2} + (\cot \alpha )^\frac {p}{2} = (\tan \alpha )^\frac {1}{2^{n-1}} + (\cot \alpha )^\frac {1}{2^{n-1}} \end{align*}
where \(p = \frac {1}{2^{n-2}}\). Moreover, because \(\tan \alpha = \frac {\sin 2\alpha }{1 + \cos 2\alpha }\), the following equations hold. \begin{align*} (\tan \alpha )^\frac {1}{2^{n-1}} &= \left ( \frac {\sin 2\alpha }{1 + \cos 2\alpha } \right )^\frac {1}{2^{n-1}} = \left ( \frac { \frac {2}{a_1} }{ 1 + \sqrt {1 - \frac {4}{a_1^2}} } \right )^\frac {1}{2^{n-1}} \\ &= \left ( \frac {2}{a_1 + \sqrt {a_1^2 - 4}} \right )^\frac {1}{2^{n-1}} = \left ( \frac {a_1 - \sqrt {a_1^2 - 4}}{2} \right )^\frac {1}{2^{n-1}} \\ (\cot \alpha )^\frac {1}{2^{n-1}} &= \left ( \frac {1}{ \frac {2}{a_1 + \sqrt {a_1^2 - 4}} } \right )^\frac {1}{2^{n-1}} = \left ( \frac {a_1 + \sqrt {a_1^2 - 4}}{2} \right )^\frac {1}{2^{n-1}} \end{align*}
Therefore, \(a_n = \left ( \frac {a_1 - \sqrt {a_1^2 - 4}}{2} \right )^\frac {1}{2^{n-1}} + \left ( \frac {a_1 + \sqrt {a_1^2 - 4}}{2} \right )^\frac {1}{2^{n-1}}\).
This problem had lots of trigonometric properties! Although this section was quite long I think they all follow general pattern of telescoping, using characteristic equations, and using clever substitution to make the problems easier. This is it for this section, and we will see more practice problems the next section.