# 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
6 years, 8 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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 $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

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$

- 6 years, 8 months 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.

- 6 years, 8 months ago

You had finals in winter? What?

- 6 years, 8 months 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!!

- 6 years, 7 months ago

Is the procedure same even when we have the repeated roots as one of the many roots ??

- 3 years, 5 months ago

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

- 3 years, 5 months ago