Linear Recurrence Relations

I will only discuss linear recurrences.

A linear recurrence is a sequence defined by kk initial terms and a recurrence of the form xn=c1xn1+c2xn2++ckxnkx_n=c_1x_{n-1}+c_2x_{n-2}+\cdots+c_kx_{n-k} where all the cc's are constants. To solve a recurrence, we find a closed-form expression for xnx_n that does not rely on previous terms.

For a very simple example, consider the recurrence relation x1=3, xn=3xn1x_1=3,\ x_n=3x_{n-1} We can easily see that the solution is xn=3nx_n=3^n for all natural numbers nn.

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

Plugging in, we get arn=c1arn1+c2arn2++ckarnkar^n=c_1ar^{n-1}+c_2ar^{n-2}+\cdots+c_kar^{n-k} Since a,r0a,r\neq 0, we can divide by arnkar_{n-k}. rk=c1rk1+c2rk2++ckr^k=c_1r^{k-1}+c_2r^{k-2}+\cdots+c_k Moving the terms over, we get rkc1rk1c2rk2+ck=0r_k-c_1r_{k-1}-c_2r^{k-2}+\cdots-c_k=0 which is a polynomial in rr, so the solution satisfies the recurrence only if rr 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.


  1. Find the characteristic polynomial.

  2. Find the roots r1,r2,,rkr_1,r_2,\cdots,r_k of the characteristic polynomial.

  3. Assuming no multiple roots, the closed-form expression will look like xn=a1(r1)n+a2(r2)n++ak(rk)nx_n=a_1(r_1)^n+a_2(r_2)^n+\cdots+a_k(r_k)^n for some constant aa's.

  4. Use the initial values to find the values of the aa's.


Let us try an example:


The sequence xnx_n is defined by x0=1x_0=1, x1=3x_1=3, and xn=5xn1+6xn2x_n=5x_{n-1}+6x_{n-2} for all n2n\ge 2. Find a closed-form expression for xnx_n.


The characteristic polynomial is found by letting the lowest indexed term in the recurrence be xkx_k, and replacing all xix_i's with xikx^{i-k}. In this case, xn=5xn1+6xn2    x2=5x+6    x25x6=0x_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-1 and 66. Thus, the closed-form expression looks like xn=a1(1)n+a2(6)nx_n=a_1(-1)^n+a_2(6)^n Plugging in n=0n=0, 1=a1+a21=a_1+a_2 Plugging in n=1n=1, 3=a1+6a23=-a_1+6a_2 Solving, we get a1=37a_1=\frac{3}{7} and a2=47a_2=\frac{4}{7}, and the closed-form expression is xn=37(1)n+47(6)nx_n=\dfrac{3}{7}(-1)^n+\dfrac{4}{7}(6)^n This can be verified by plugging it into the recurrence.


Problems:

  1. Make up your own recurrences and solve them!

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

Note by Daniel Chiu
5 years, 9 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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 \( ... \) or \[ ... \] 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

After reading this, I have a question: You have shown that xn=a1(r1)n++ak(rk)n 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?

Calvin Lin Staff - 5 years, 9 months ago

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?

Daniel Chiu - 5 years, 9 months ago

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 kk initial starting values, we can find kk variables which satisfy the equations. What kind of equations are these? Exponential? Polynomial? Linear? Hence, how would you solve this system?

Hint: VD

Calvin Lin Staff - 5 years, 9 months ago

Log 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

Shivin Srivastava - 5 years, 9 months ago

Log in to reply

We could apply recurrence relations by reverse engineering: When we see something like A(a+bc)n+B(abc)nA(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+bc,abca+b\sqrt {c},a-b\sqrt {c} are two roots of a quadratic, so our recursive formula consists of three "variables".

Xuming Liang - 5 years, 9 months ago

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 an=6an19an2,a0=0,a1=1 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 x26x+9=0 x^2 - 6x+9 = 0 so (x3)2=0 (x-3)^2 = 0 , so x=3 x=3 . Clearly if we write an=b1(3n)+b2(3n) a_{n} = b_{1}(3^n) + b_{2}(3^n) to take into account the repeated root we can just factorise out the 3n 3^n . So we just need to solve an=b(3n) a_{n} = b (3^n) . However, plugging in values of a1,a2 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

Josh Rowley - 5 years, 9 months ago

Log in to reply

The problem is that there is a multiple root, which then you have to take an=b1(3n)+b2n(3n)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!

Daniel Chiu - 5 years, 9 months ago

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.

Akshunna Shaurya - 5 years, 8 months ago

Log in to reply

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

兰 恩浩 - 5 years, 3 months ago

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} ??

nikhil pachisia - 4 years, 11 months ago

Log in to reply

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

Calvin Lin Staff - 4 years, 10 months ago

Log in to reply

precise and useful.Thanks for posting it.

Yunhao King - 4 years, 7 months ago

Log in to reply

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

Susant Rautray - 2 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...