Waste less time on Facebook — follow Brilliant.
×

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, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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\) Aditya Raut · 3 years, 3 months ago

Log in to reply

i think there is a small error

If there is a repeated root r of the characteristic polynomial with multiplicity m , then the closed-form expression will look like

in the closed form the power of n is one less than the term but in last term there is an error Sundara Narasimhan · 2 weeks ago

Log in to reply

Is the procedure same even when we have the repeated roots as one of the many roots ?? Sundara Narasimhan · 2 weeks ago

Log in to reply

: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!! Finn Hulse · 3 years, 2 months ago

Log in to reply

You had finals in winter? What? Tanishq Aggarwal · 3 years, 3 months ago

Log in to reply

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. Rahul Saha · 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...