×

# 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.

Note by Daniel Chiu
3 years, 1 month ago

Sort by:

Hey can you please post a way to solve this kind of recurrences ??? @Daniel Chiu

$$a_n=na_{n-1}+a_{n-2}$$

$$a_n=a_{n-1}^2+a_{n-2}$$

$$a_n=a_{n-1}^2+a_{n-2}^2$$ · 3 years, 1 month ago

:O... I kind of understood this. It was pretty good dude! Hey, do you know that you're in like 13 different articles in the news... How did you get so good at math? Like seriously!! · 3 years ago

You had finals in winter? What? · 3 years, 1 month ago

If I want to find the recurrence relation for $$n^2+2^n$$,should I just reverse the steps or is there an easier way?I think looking at the differences will help. · 3 years, 1 month ago