Strange recursions

Find explicit formulas for the nth term of each of the following sequences:

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: Immediately, we may state that the characteristic polynomial is and now we can see that it has one zero, at $x=1$. Thus our general solution should be 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 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 where $A$ and $B$ are constants. Now we may solve for the coefficients $A$ and $B$: so we have which means that 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: The characteristic polynomial here is 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 Using the initial conditions, we have which gives us and so we have, as our final answer,

Now we can start on the scary-looking problems. First, we have 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 and so if we define an entirely new sequence $c'_n$ as $c'_n=e^{c_n}$, we have Look, it's the Fibonacci sequence! I won't bother to write in the messy Fibonacci explicit formula - I'll just write This implies that Yay, we did it! Not so scary after all. Let's try the next one with the same strategy:

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

That wasn't so bad, was it? The next one is a bit trickier: 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... Yes, that's it! Of course! If we take the arctangent of both sides of our recursion, we have ...and now the substitution is obvious. If we let $e'_n=\arctan e_n$, and so

One more to go! The next one is 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: This will give you or, by rearranging the recurrence, and so, with the initial conditions, and 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.