Skip to page content Home     Posts     CV     Contact     People

Strange recursions

Find explicit formulas for the nth term of each of the following sequences: $$a_n=2a_{n-1}-a_{n-2},\space\space\space a_0=1, \space a_1=2$$ $$b_n+6b_{n-1}+9b_{n-2}=0, \space\space\space b_0=1,\space b_1=2$$ $$c_n=\ln(e^{c_{n-1}}+e^{c_{n-2}}), \space\space\space c_0=c_1=0$$ $$d_n=\frac{d_{n-1}d_{n-2}}{d_{n-1}+d_{n-2}}, \space\space\space d_0=d_1=1$$ $$e_n=\frac{e_{n-1}+e_{n-2}}{1-e_{n-1}e_{n-2}},\space\space\space e_0=e_1=2$$ $$f_n=\sqrt{f_{n-1}+2}, \space\space\space f_0=0$$

Don't be alarmed by these crazy-looking sequences! By the end of this post, you'll know how to find explicit formulas for all of them. If you haven't already, I advise you to go back and read my post "solving difference equations", because we will use strategies discussed there to solve these problems.

When you try to solve them on your own, I suggest that you calculate the next couple terms and try to form a conjecture about

The first two don't look so threatening - they're just like the ones we did in the other post. Let's start with the first one: $$a_n=2a_{n-1}-a_{n-2},\space\space\space a_0=1, \space a_1=2$$ Immediately, we may state that the characteristic polynomial is $$x^2-2x+1$$ and now we can see that it has one zero, at $x=1$. Thus our general solution should be $$a_n=A$$ for some constant $A$.

Uh oh, there's a problem! Look at our initial conditions - they aren't the same, so the sequence can't be constant. Was there something wrong with our old strategy?

As it turns out, there was something wrong with it. That strategy only works for sequences whose characteristic polynomials only have single roots, but this polynomial has a double root at $x=1$. What can we do now?

Notice that if we look only at the recursive formula and not at the initial conditions, we might notice that $$a_n=n$$ satisfies the recursive formula, since $2(n-1)-(n-2)=n$. As discussed in the other post, any linear combination of particular solutions is also a particular solution. So, since $a_n=n$ satisfies the recursive formula, so does $$a_n=A+Bn$$ where $A$ and $B$ are constants. Now we may solve for the coefficients $A$ and $B$: $$a_0=A=1$$ $$a_1=A+B=2$$ so we have $$A=1, \space B=1$$ which means that $$a_n=n+1$$ It sure seems simple now, doesn't it? We could have easily calculated the next few terms and then proven an easily-formed conjecture by induction... but this is not so easy with other problems of this type. For example, if a characteristic polynomial ends up having a triple root $r$, the terms satisfying the recursion are $A$, $Br$, and $Cr^2$.

Now we will move on to the next problem, which is solved similarly: $$b_n+6b_{n-1}+9b_{n-2}=0, \space\space\space b_0=1,\space b_1=2$$ The characteristic polynomial here is $$x^2+6x+9$$ and it has a double root at $x=-3$. It is easily verified that $(-3)^n$ and $n(-3)^n$ solve the recursion, so we have $$b_n=A(-3)^n+Bn(-3)^n$$ Using the initial conditions, we have $$b_0=A=1$$ $$b_1=-3A-3B=2$$ which gives us $$A=1,\space B=-\frac{5}{3}$$ and so we have, as our final answer, $$b_n=(-3)^n-\frac{5}{3}n(-3)^n$$

Now we can start on the scary-looking problems. First, we have $$c_n=\ln(e^{c_{n-1}}+e^{c_{n-2}}), \space\space\space c_0=c_1=0$$ To solve this, I will employ substitution - a new method for solving recurrence relations that we have not used before. Notice that if we exponentiate both sides of the recurrence, we get $$e^{c_n}=e^{c_{n-1}}+e^{c_{n-2}}$$ and so if we define an entirely new sequence $c'_n$ as $c'_n=e^{c_n}$, we have $$c'_n=c'_{n-1}+c'_{n-2}, \space\space\space c'_0=c'_1=1$$ Look, it's the Fibonacci sequence! I won't bother to write in the messy Fibonacci explicit formula - I'll just write $$c'_n=F_n$$ This implies that $$e^{c_n}=F_n$$ $$c_n=\ln (F_n)$$ Yay, we did it! Not so scary after all. Let's try the next one with the same strategy:

$$d_n=\frac{d_{n-1}d_{n-2}}{d_{n-1}+d_{n-2}}, \space\space\space d_0=d_1=1$$

After a bit of analysis, one might notice that the recursive formula is equivalent to $$\frac{1}{d_n}=\frac{1}{d_{n-1}}+\frac{1}{d_{n-2}}$$ and so, if we define $d'_n=\frac{1}{d_n}$, $$d'_n=d'_{n-1}+d'_{n-2}, \space\space\space d'_0=d'_1=1$$ Look, it's Fibonacci again! Hooray! Now we have $$d'_n=F_n$$ $$\frac{1}{d_n}=F_n$$ $$d_n=\frac{1}{F_n}$$

That wasn't so bad, was it? The next one is a bit trickier: $$e_n=\frac{e_{n-1}+e_{n-2}}{1-e_{n-1}e_{n-2}},\space\space\space e_0=e_1=2$$ The substitution to make in this one is very difficult to spot. If you look at it for a while, it might begin to look like something familiar... $$\tan(\theta+\phi)=\frac{\tan\theta+\tan\phi}{1-\tan\theta\tan\phi}$$ Yes, that's it! Of course! If we take the arctangent of both sides of our recursion, we have $$\arctan e_n=\arctan \frac{e_{n-1}+e_{n-2}}{1-e_{n-1}e_{n-2}}$$ $$\arctan e_n=\arctan e_{n-1}-\arctan e_{n-2}$$ ...and now the substitution is obvious. If we let $e'_n=\arctan e_n$, $$e'_n=e'_{n-1}+e'_{n-2}, \space\space\space e'_0=e'_1=\arctan 2$$ and so $$e'_n=F_n\arctan 2$$ $$\arctan e_n=F_n\arctan 2$$ $$e_n=\tan(F_n\arctan 2)$$

One more to go! The next one is $$f_n=\sqrt{f_{n-1}+2}, \space\space\space f_0=0$$ The substitution here may not be clear either, but here's a hint - it also uses trigonometric functions. If you haven't already, try and solve this one.

Ready? Here's the substitution you should make: $$f'_n=\arccos \frac{f_n}{2}$$ This will give you $$2\cos f'_n=\sqrt{2\cos f'_{n-1}+2},\space\space\space f'_0=\frac{\pi}{2}$$ or, by rearranging the recurrence, $$2\cos f'_n=2\sqrt{\frac{\cos f'_{n-1}+1}{2}}$$ $$2\cos f'_n=2\cos \frac{f'_{n-1}}{2}$$ $$f'_n=\frac{f'_{n-1}}{2}$$ and so, with the initial conditions, $$f'_n=\pi 2^{-n-1}$$ and $$\arccos \frac{f_n}{2}=\pi 2^{-n-1}$$ $$\frac{f_n}{2}=\cos(\pi 2^{-n-1})$$ $$f_n=2\cos(\pi 2^{-n-1})$$ Hooray, we've done it! That's all I have for you now, but in the near future, I'm sure I'll return to this topic.