Recurrence Relations (Part 2)

First of all, sorry for not posting for two weeks. I had finals and was busy (also I lost my 80 day streak :O). Well, I'll try to start up again by continuing on recurrence relations.

Here is my second post on recurrence relations. You can find part 1 here. For a review problem, see here.

Now, we will continue from last time to try to solve recurrence relations with two more complications:

1. Some terms are not previous elements of the sequence.

2. There are repeated roots of the characteristic polynomial.

1: Some terms are not previous elements of the sequence.

The idea for recurrences that satisfy this complication is to remove the term that is not a previous element in the sequence, and then solve as we would before. You can do this by shifting the index, which means plugging a different index into the recurrence, and then usually subtracting the two resulting equations.

A sequence $a_0,a_1,\cdots$ is defined by $a_0=0$ and $a_n=2a_{n-1}+1$ for $n\ge 1$. Find a closed-form expression for $a_n$.

A recurrence must hold for all possible values of $n$, so if we change $n$ to $n+1$, the recurrence still holds. To shift the index, add 1 (or subtract 1) to each index of the recurrence. We get $a_{n+1}=2a_n+1$ Subtracting the two equations, the 1's cancel, and we are left with a recurrence as we have had before: $a_{n+1}-a_n=2a_n-2a_{n-1}$ $a_{n+1}=3a_n-2a_{n-1}$ The characteristic polynomial is $x^2-3x+2=(x-2)(x-1)$. Therefore, the closed-form expression can be expressed as $a_n=c_1(2^n)+c_2$. We only have one initial condition, but need two! Fortunately, the recurrence given only uses one previous term, so we can find that $a_1=1$. Now, we can solve that $c_1=1$ and $c_2=-1$.

Therefore, the closed-form expression is $a_n=2^n-1$

This method can also solve recurrences with terms of powers of $n$. With each shift, the power goes down by one until the term is gone.

A sequence $a_0,a_1,\cdots$ is defined by $a_0=0$ and $a_n=3a_{n-1}+2^n$ for $n\ge 1$. Find a closed-form expression for $a_n$.

Similar to last time, we try to eliminate the term that isn't a previous element, which is $2^n$. Again, we shift the index: $a_{n+1}=3a_n+2^{n+1}$ Thinking cleverly, we note that $2^{n+1}-2(2^n)=0$, and so we subtract twice the original recurrence from this new recurrence: $a_{n+1}-2a_n=3a_n+2^{n+1}-6a_{n-1}-2(2^n)=3a_n-6a_{n-1}$ $a_{n+1}=5a_n-6a_{n-1}$ This is a recurrence we know how to deal with. The characteristic polynomial is $x^2-5x+6=(x-3)(x-2)$, so the closed-form expression can be expressed as $c_1(2^n)+c_2(3^n)$. We can find another initial term using the given recurrence, $a_1=2$. Solving, we find the closed form is $a_n=2(3^n)-2(2^n)$

Now, we see how to solve recurrences given any exponential terms. Shift the index once, then subtract to remove the exponentials.

2: There are repeated roots of the characteristic polynomial.

If there is a repeated root $r$ of the characteristic polynomial with multiplicity $m$, then the closed-form expression will look like $c_1(r)^n+c_2n(r)^n+c_3n^2r^n+\cdots+c_mn^mr^n$ See here on more why this is so.

A sequence $a_0,a_1,\cdots$ is defined by $a_0=1$, $a_1=6$, and $a_n=4a_{n-1}-4a_{n-2}$ for $n\ge 2$. Find a closed-form expression for $a_n$.

The characteristic polynomial is $x^2-4x+4=(x-2)^2$. Using our above form, we see that the closed-form expression looks like $a_n=c_1(2^n)+c_2n(2^n)$. From the initial conditions, $c_1=1$ $2c_1+2c_2=6$ so $c_1=1$ and $c_2=2$. Thus, the closed-form expression is $a_n=2^n+2n(2^n)$.

Problems:

1. Make up your own recurrences and solve them! (once again!)

I'll post a problem or two soon.

Thanks for reading! This will be my last post on recurrence relations.