I will only discuss *linear* recurrences.

A *linear recurrence* is a sequence defined by \(k\) initial terms and a recurrence of the form
\[x_n=c_1x_{n-1}+c_2x_{n-2}+\cdots+c_kx_{n-k}\]
where all the \(c\)'s are constants. To solve a recurrence, we find a closed-form expression for \(x_n\) that does not rely on previous terms.

For a very simple example, consider the recurrence relation \[x_1=3,\ x_n=3x_{n-1}\] We can easily see that the solution is \(x_n=3^n\) for all natural numbers \(n\).

Geometric series (or combinations, as we will see) are usually the solutions to recurrences. Now, let us say we have a recurrence \[x_n=c_1x_{n-1}+c_2x_{n-2}+\cdots+c_kx_{n-k}\] and a solution \(x_n=ar^n\).

Plugging in, we get
\[ar^n=c_1ar^{n-1}+c_2ar^{n-2}+\cdots+c_kar^{n-k}\]
Since \(a,r\neq 0\), we can divide by \(ar_{n-k}\).
\[r^k=c_1r^{k-1}+c_2r^{k-2}+\cdots+c_k\]
Moving the terms over, we get
\[r_k-c_1r_{k-1}-c_2r^{k-2}+\cdots-c_k=0\]
which is a polynomial in \(r\), so the solution satisfies the recurrence only if \(r\) is a root of this polynomial. This polynomial is called the *characteristic polynomial* of the recurrence.

Also, note that if two geometric series satisfy a recurrence, the sum of them also satisfies the recurrence. Then, we can find the following method for solving recurrences.

Find the characteristic polynomial.

Find the roots \(r_1,r_2,\cdots,r_k\) of the characteristic polynomial.

Assuming no multiple roots, the closed-form expression will look like \[x_n=a_1(r_1)^n+a_2(r_2)^n+\cdots+a_k(r_k)^n\] for some constant \(a\)'s.

Use the initial values to find the values of the \(a\)'s.

Let us try an example:

The sequence \(x_n\) is defined by \(x_0=1\), \(x_1=3\), and \(x_n=5x_{n-1}+6x_{n-2}\) for all \(n\ge 2\). Find a closed-form expression for \(x_n\).

The characteristic polynomial is found by letting the lowest indexed term in the recurrence be \(x_k\), and replacing all \(x_i\)'s with \(x^{i-k}\). In this case, \[x_n=5x_{n-1}+6x_{n-2}\implies x^2=5x+6\implies x^2-5x-6=0\] Factoring the characteristic polynomial, we get roots of \(-1\) and \(6\). Thus, the closed-form expression looks like \[x_n=a_1(-1)^n+a_2(6)^n\] Plugging in \(n=0\), \[1=a_1+a_2\] Plugging in \(n=1\), \[3=-a_1+6a_2\] Solving, we get \(a_1=\frac{3}{7}\) and \(a_2=\frac{4}{7}\), and the closed-form expression is \[x_n=\dfrac{3}{7}(-1)^n+\dfrac{4}{7}(6)^n\] This can be verified by plugging it into the recurrence.

Problems:

- Make up your own recurrences and solve them!

Click here for more on this topic. Thanks for reading!

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestAfter reading this, I have a question: You have shown that \( x_n = a_1 (r_1)^ n + \ldots + a_k ( r_k ) ^ {n} \) will satisfy the equation. Why must all solutions be of this (seemingly exponential) form? Why isn't it possible to have a logarithmic or trigonometric term in there?

Log in to reply

Well, the sequence is uniquely determined (just use the recurrence), so if a exponential form satisfies it, no other series can. All that is left to show that the system of equations always has a solution, and I cannot do this (and searching cannot find a proof). Can anyone do this?

Log in to reply

Good thought process. You're close to the answer (for linear recurrence with distinct roots).

You want to show that given any \(k \) initial starting values, we can find \(k\) variables which satisfy the equations. What kind of equations are these? Exponential? Polynomial? Linear? Hence, how would you solve this system?

Hint:VDLog in to reply

well i don't about logarithmic but if you get the roots of the characteristic equation to be imaginary, then the relation will be trigonometric in relation (using Euler's formula). yeah but this method is not in any case general. for example it cant be used to solve a(n+1)= a(n) + 1/a(n). given a(1)=1

Log in to reply

Why the closed-form expression will look like so ,in step three?

Log in to reply

Hi Daniel. After reading this post I decided to have a go at solving some recursions myself, and helpfully this https://brilliant.org/discussions/thread/recurrence-relations-from-inmo-camp-for-maharashtr/?ref_id=75599 had just popped up on my feed. Question 1b) states: Solve \[ a_{n} = 6a_{n-1} - 9a_{n-2}, a_{0} = 0, a_{1}=1 \] which I believe is a linear recurrence. So, forming the characteristic polynomial we get \[ x^2 - 6x+9 = 0 \] so \[ (x-3)^2 = 0 \], so \( x=3 \). Clearly if we write \( a_{n} = b_{1}(3^n) + b_{2}(3^n) \) to take into account the repeated root we can just factorise out the \( 3^n \). So we just need to solve \( a_{n} = b (3^n) \). However, plugging in values of \( a_{1}, a_{2} \) etc. we just get many contradictions and the equation is thus unsolvable. I would really appreciate it if you would point out where my logical error is or where this method breaks down. Thanks in advance

Log in to reply

The problem is that there is a multiple root, which then you have to take \[a_n=b_1(3^n)+b_2n(3^n)\] I was planning to do that in two weeks. I did notice that post, and also note some of those are not linear so it is different.

I'm glad you are applying this though!

Log in to reply

When you say multiple root, I am assuming that you mean same roots in both cases(because a quadratic equation will always have multiple,ie 2, roots. I have always preferred using "repeated roots"). Can you tell us why a characteristic equation with equal roots fails here. and why do we add a "n"to b2.

Log in to reply

We could apply recurrence relations by reverse engineering: When we see something like \(A(a+b\sqrt {c})^n+B(a-b\sqrt {c})^n\), which a lot of times appears in solving Pell's equation, it's tempting to build an recursive formula from it, so that it's easier to generate solutions. Note that \(a+b\sqrt {c},a-b\sqrt {c}\) are two roots of a quadratic, so our recursive formula consists of three "variables".

Log in to reply

Why if two geometric series satisfy a recurrence, the sum of them also satisfies the recurrence? Please elucidate.

Log in to reply

precise and useful.Thanks for posting it.

Log in to reply

@Daniel Chiu Can you help edit this into the Linear Recurrence Wiki? Thanks!

Log in to reply

I have a doubt in a question ( a

{0}=0 and a{n} = 3a{n-1} + 1 ). to find a{2010} ??Log in to reply