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 a0,a1,a_0,a_1,\cdots is defined by a0=0a_0=0 and an=2an1+1a_n=2a_{n-1}+1 for n1n\ge 1. Find a closed-form expression for ana_n.


A recurrence must hold for all possible values of nn, so if we change nn to n+1n+1, the recurrence still holds. To shift the index, add 1 (or subtract 1) to each index of the recurrence. We get an+1=2an+1a_{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: an+1an=2an2an1a_{n+1}-a_n=2a_n-2a_{n-1} an+1=3an2an1a_{n+1}=3a_n-2a_{n-1} The characteristic polynomial is x23x+2=(x2)(x1)x^2-3x+2=(x-2)(x-1). Therefore, the closed-form expression can be expressed as an=c1(2n)+c2a_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 a1=1a_1=1. Now, we can solve that c1=1c_1=1 and c2=1c_2=-1.

Therefore, the closed-form expression is an=2n1a_n=2^n-1

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


A sequence a0,a1,a_0,a_1,\cdots is defined by a0=0a_0=0 and an=3an1+2na_n=3a_{n-1}+2^n for n1n\ge 1. Find a closed-form expression for ana_n.


Similar to last time, we try to eliminate the term that isn't a previous element, which is 2n2^n. Again, we shift the index: an+1=3an+2n+1a_{n+1}=3a_n+2^{n+1} Thinking cleverly, we note that 2n+12(2n)=02^{n+1}-2(2^n)=0, and so we subtract twice the original recurrence from this new recurrence: an+12an=3an+2n+16an12(2n)=3an6an1a_{n+1}-2a_n=3a_n+2^{n+1}-6a_{n-1}-2(2^n)=3a_n-6a_{n-1} an+1=5an6an1a_{n+1}=5a_n-6a_{n-1} This is a recurrence we know how to deal with. The characteristic polynomial is x25x+6=(x3)(x2)x^2-5x+6=(x-3)(x-2), so the closed-form expression can be expressed as c1(2n)+c2(3n)c_1(2^n)+c_2(3^n). We can find another initial term using the given recurrence, a1=2a_1=2. Solving, we find the closed form is an=2(3n)2(2n)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 rr of the characteristic polynomial with multiplicity mm, then the closed-form expression will look like c1(r)n+c2n(r)n+c3n2rn++cmnmrnc_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 a0,a1,a_0,a_1,\cdots is defined by a0=1a_0=1, a1=6a_1=6, and an=4an14an2a_n=4a_{n-1}-4a_{n-2} for n2n\ge 2. Find a closed-form expression for ana_n.


The characteristic polynomial is x24x+4=(x2)2x^2-4x+4=(x-2)^2. Using our above form, we see that the closed-form expression looks like an=c1(2n)+c2n(2n)a_n=c_1(2^n)+c_2n(2^n). From the initial conditions, c1=1c_1=1 2c1+2c2=62c_1+2c_2=6 so c1=1c_1=1 and c2=2c_2=2. Thus, the closed-form expression is an=2n+2n(2n)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
5 years, 4 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

an=nan1+an2a_n=na_{n-1}+a_{n-2}

an=an12+an2a_n=a_{n-1}^2+a_{n-2}

an=an12+an22a_n=a_{n-1}^2+a_{n-2}^2

Aditya Raut - 5 years, 4 months ago

Log in to reply

If I want to find the recurrence relation for n2+2nn^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 - 5 years, 4 months ago

Log in to reply

You had finals in winter? What?

Tanishq Aggarwal - 5 years, 4 months 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 - 5 years, 3 months 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 years, 1 month 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 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...