Second Order Recurrence Relation

The Characteristic Technique of solving second-order recurrence relations is similar to that of solving first-order recurrence relations. It involves deriving the complementary function then finding a suitable particular solution to solve for the closed-form of a given second-order recurrence relation. The Fibonacci sequence is a second order recurrence relation that can be solved using the Characteristic technique to find its closed form equation.

Get started Sign up for free
Second Order Recurrence Relation Second Order Recurrence Relation

Create learning materials about Second Order Recurrence Relation with our free learning app!

  • Instand access to millions of learning materials
  • Flashcards, notes, mock-exams and more
  • Everything you need to ace your exams
Create a free account

Millions of flashcards designed to help you ace your studies

Sign up for free
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

How do you find the reduced equation of a recurrence relation of the form \(u_{n+2} =a_1u_{n+1}+a_2u_n+f(n)\)?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which term best describes the following recurrence relation? \(u_{n+2}=2u_{n+1}+3u_n+4n+12\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

What form would the particular solution of the following recurrence relation take? \(u_{n+2}=2u_{n+1}+u_n+1\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which term best describes the following recurrence relation? \(u_{n+2}=6u_{n+1}-9u_n\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which term best describes the following recurrence relation? \(u_{n+2}=2u_{n+1}+3u_n+n^2\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which of the following is the correct form for the particular solution of the recurrence relation \(u_{n+2}=6u_{n+1}-9u_n\)?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

What would be the form for the particular solution of the recurrence relation \(u_{n+2}=u_{n+1}+5u_n+n^2+2n+1\)?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which is the correct form for the particular solution of the following recurrence relation? \(u_n=3u_{n-1}+u_{n-2}+3\times 4^n\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

What is the method used to solve second-order recurrence relations?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

How many initial values/boundary conditions do you need to solve a second-order recurrence relation?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

How do you find the reduced equation of a recurrence relation of the form \(u_{n+2} =a_1u_{n+1}+a_2u_n+f(n)\)?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which term best describes the following recurrence relation? \(u_{n+2}=2u_{n+1}+3u_n+4n+12\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

What form would the particular solution of the following recurrence relation take? \(u_{n+2}=2u_{n+1}+u_n+1\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which term best describes the following recurrence relation? \(u_{n+2}=6u_{n+1}-9u_n\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which term best describes the following recurrence relation? \(u_{n+2}=2u_{n+1}+3u_n+n^2\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which of the following is the correct form for the particular solution of the recurrence relation \(u_{n+2}=6u_{n+1}-9u_n\)?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

What would be the form for the particular solution of the recurrence relation \(u_{n+2}=u_{n+1}+5u_n+n^2+2n+1\)?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

Which is the correct form for the particular solution of the following recurrence relation? \(u_n=3u_{n-1}+u_{n-2}+3\times 4^n\).

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

What is the method used to solve second-order recurrence relations?

Show Answer
  • + Add tag
  • Immunology
  • Cell Biology
  • Mo

How many initial values/boundary conditions do you need to solve a second-order recurrence relation?

Show Answer

Convert documents into flashcards for free with AI!

Contents
Table of contents

    Meaning of Second order recurrence relations

    Whenever you are describing a relation of events that require any information from different time positions, you are talking about recurrence relations. Now, second order recurrence relations are relations that require information two steps behind to get the information you want.

    Second-order recurrence relations are recurrence relations of the form \[u_{n+2}=Au_{n+1}+B u_{n}+f(n),\] for all integers \(n\) greater than some fixed integer, \(A\) and \(B\) are constants and \(f(n)\) is a polynomial.

    Examples of second order recurrence relations are,

    • \(u_{n+2}=2u_{n+1}-u_{n}+3\),
    • \(u_{n}=u_{n-1}-4u_{n-2}\),
    • \(u_{n+1}=-4u_{n}+7u_{n-1}+n^2\).

    Second order recurrence relations are classified into homogeneous and non-homogeneous recurrence relations.

    Homogeneous second order recurrence relations

    Homogeneous second order relations are relations that only show a relation between the terms of the sequence at different iterations.

    Homogeneous second-order recurrence relations are of the form\[u_{n+2}=Au_{n+1}+Bu_{n}\] for all integers \(n\) greater than some fixed integer, \(A\) and \(B\) are constants.

    Examples of homogeneous second order recurrence relations are,

    • \(u_{n+2}=2u_{n+1}-u_{n}\),
    • \(u_{n}=u_{n-1}-4u_{n-2}\),
    • \(u_{n+1}=-4u_{n}+7u_{n-1}\).

    Non-homogeneous second order recurrence relations

    Non-homogeneous second order relations are relations that show a relation between the terms of the sequence at different iterations having a bit of extra information, generally a polynomial in terms of \(n\). In fact, this is the general definition introduced at the very first paragraph of this article.

    Non- homogeneous second-order recurrence relations are recurrence relations of the form \[u_{n+2}=Au_{n+1}+B u_{n}+f(n),\] for all integers \(n\) greater than some fixed integer, \(A\) and \(B\) are constants and \(f(n)\) is a polynomial.

    Examples of non-homogeneous second order recurrence relations are,

    • \(u_{n+2}=2u_{n+1}-u_{n}+3\),
    • \(u_{n}=u_{n-1}-4u_{n-2}+n+1\),
    • \(u_{n+1}=9u_{n}+3u_{n-1}-7n^2\)

    Solving second order recurrence relations

    When solving a second order recurrence relation of the form

    \[u_{n+2}=Au_{n+1}+B u_{n}+f(n),\]

    we look for an expression of the \(n^{\text{th}}\) term, that takes the form

    \[u_{n}=c(n)+p(n),\]

    where \(c(n)\) is the complementary function and \(p(n)\) is the particular function.

    The very first step to solving second order recurrence relations, is to solve its homogeneous part, also called the reduced equation. Hiding \(f(n)\) will lead you to the homogenous part of a recurrence relation,

    \[u_{n+2}=Au_{n+1}+B u_{n}, \]

    and solving this part would require you to find what we call the complementary function \(c(n).\)

    Now, to find the complementary function, we proceed as follow. We are looking for an expression of the form \(u_{n}=r^n\) where \(u_{n}\) satisfies

    \[u_{n+2}=Au_{n+1}+B u_{n}. \]

    Substituting in will lead to

    \[\begin{align} u_{n+2}&=Au_{n+1}+Bu_{n} \\ r^{n+2}&=Ar^{n+1}+Br^{n}\\ r^2-Ar-B&=0\end{align}\]

    \(r^2-Ar-B=0\) is called the characteristic equation and the number of solutions it has will determine the general form of the complementary function \(c(n).\)

    We distinguish three cases for the characteristic equation \(r^2-Ar-B=0.\)

    • If \(r^2-Ar-B=0\) has two distinct real solutions \(r_1\) and \(r_2\), then \[u_n=Cr_{1}^n+Dr_{2}^n,\] for some constants \(C\) and \(D\).
    • If \(r^2-Ar-B=0\) has a double root \(r\), then \[u_n=Cr^n+Dnr^n.\]
    • If \(r^2-Ar-B=0\) has two complex roots \(z_1\) and \(z_2\), then \[u_n=C z_1^n+Dz_2^n,\] for some constants \(C\) and \(D\).

    As for the particular solution \(p(n)\), it takes the form of the polynomial \(f(n).\)

    Now, let's get the job done and recap the steps of calculation!

    Step 1. Find the reduced equation by setting \(f(n)=0\).

    For homogenous recurrence relations the reduced equation is the same as the recurrence relation equation. This gives you an equation of the form \(u_{n+2}=Au_{n+1}+Bu_{n}\).

    Step 2. Find the characteristic equation and solve for \(r\).

    Step 3. Find the complementary function using the values of the \(r\).

    Real and distinct roots \(r_{1}\) and \(r_{2}\) \(c(n)=Cr_{1}^{n}+D r_{2}^{n}\)
    Repeated real roots \(r_{1}=r_{2}=r\)\(c(n)=Cr^{n}+Dnr^{n}\)
    Complex roots \(r_1=z_1\) and \(r_{2}=z_2\)\(c(n)=C z_1^n+D z_2^n \)

    Step 4. Find the general form of particular solution and substitute in \(p(n)=u_{n}\) into the original equation and solve for unknowns.

    Step 5. Using the initial value given in the question, find the value of \(C\) and \(D\).

    Examples are always a good idea to understand the topic, so here we go!

    Example of Solving a Second Order Non-Homogenous Recurrence Relation with Real Distinct Roots

    Solve the recurrence relation \(u_{n+2}=2u_{n+1}+3u_{n}+4n+12\) with initial values \(u_{1}=-1\) and \(u_{2}=16\).

    Solution

    Step 1. Find the reduced equation by setting \(f(n)=0\), to get

    $$u_{n+2}=2u_{n+1}+3u_n.$$

    Step 2. Find the characteristic equation and solve for \(r\).

    The characteristic equation is given by \(r^2-2r-3=0,\) solving it we get \(r_1=-1\) and \(r_2=3.\)

    Step 3. Find the complementary function \(c(n).\)

    \[c(n)=Cr_1^{n}+Dr_2^{n}=C(-1)^n+D 3^n\]

    Step 4. Find the form of particular solution and substitute in \(p(n)=u_{n}\) into the original equation and solve for unknowns.

    Since \(f(n)=4n+12\), the particular solution takes the form \(p(n)=an+b\).

    Set \(p(n)=u_n=an+b\), therefore, \(p(n+1)=u_{n+1}=a(n+1)+b\) and \(p(n+2)=u_{n+2}=a(n+2)+b\).

    Substituting these into the original equation gives us

    \[\begin{align} u_{n+2}&=2u_{n+1}+3u_n+4n+12 \\ a(n+2)+b&=2(a(n+1)+b)+3(an+b)+4n+12 \\ an+2a+b&=2an+2a+2b+3an+3b+4n+12 \end{align}\]

    To solve for \(a\) and \(b\), you compare coefficients.

    Comparing coefficients of \(n\) gives,

    \[\begin{align} a&=2a+3a+4 \\ a&=-1 \end{align}\]

    Comparing constant terms gives,

    \[\begin{align} 2a+b&=2a+2b+3b+12 \\ b&=-3 \end{align}\]

    Therefore, the particular solution is \(p(n)=-n-3.\)

    The general solution is thus \(u_n=C(-1)^n+D3^{n}-n-3.\)

    Step 5. Using the initial values given in the question, find the values of \(C\) and \(D\).

    Since the initial values are \(u_{1}=-1\) and \(u_{2}=16\), we have

    \[\begin{align} u_1=-1&=C(-1)+D(3)-1-3 \\ -C+3D&=3\end{align}\]

    \[\begin{align} u_2=16&=C(-1)^2+3^2D-2-3 \\ C+9D&=21 \end{align}\]

    Solving the above equations simultaneously we get, \(C=3\) and \(D=2\).

    Therefore the solution is the closed-form equation,

    $$u_n=3\times (-1)^n+2\times 3^n -n-3.$$

    Example of Solving a Second-Order Homogenous Recurrence Relation with Repeated Roots

    Solve the recurrence relation \(u_{n+2}=6u_{n+1}-9u_{n}\) with initial values \(u_{1}=1\) and \(u_{2}=4\).

    Solution

    Step 1. Find the reduced equation.

    Since this is a homogeneous equation, we have $$u_{n+2}=6u_{n+1}-9u_{n}.$$

    Step 2. Find the characteristic equation and solve for \(r\).

    The characteristic equation is given by,

    \[r^2-6r-9=0\]

    Therefore, \(r_1=r_2=r=3.\)

    Step 3. Find the complementary function.

    Since we have repeated roots, the complementary function is given by,

    \[\begin{align} c(n)&= Cr^n+Dnr^n=C\times 3^n+D n\times 3^n \end{align}\]

    Step 4. Since \(f(n)=0\) there is no particular solution.

    Therefore, the general solution is \(u_{n}=(C+Dn)\times3^{n}\).

    Step 5. Using the initial values given, we find the values of \(C\) and \(D\).

    Since \(u_{1}=1\) and \(u_{2}=4\), we have

    \[\begin{align} u_1&=1=3(C+D)=3C+3D\\ u_{2}&=4=9(C+2D)=9C+18D\end{align}\]

    Solving simultaneously gives,

    $$C=\frac{2}{9}, D=\frac{1}{9}.$$ Therefore,

    $$ u_{n}=\left(\frac{2}{9}+\frac{n}{9}\right)\times3^{n}.$$

    Example of Solving a Second-Order Homogenous Recurrence Relation with Complex Roots

    Solve the recurrence relation \(u_{n+2}=8u_{n+1}-41u_{n}\) with initial values \(u_{1}=24\) and \(u_{2}=-54\).

    Solution

    Step 1. Find the reduced equation.

    Since this is a homogeneous equation, we have $$u_{n+2}=8u_{n+1}-41u_n.$$

    Step 2. Find the characteristic equation and solve for \(r\).

    The characteristic equation is given by \[r^2-8r-41=0,\] thus \(r_1=z_1=4+5i\) and \(r_2=z_2=4-5i\).

    Step 3. Find the complementary function.

    \[\begin{align} c(n)&=Cz_{1}^{n}+Dz_{2}^{n} \\ &=C(4+5i)^n+D(4-5i)^n. \end{align}\]

    Step 4. Find the particular solution.

    Since \(f(n)=0\), there is no particular solution.

    Now we have a general solution, \(u_n=C(4+5i)^n+D(4-5i)^n\).

    Step 5. Using the initial values given in the question, find the values of \(C\) and \(D.\)

    Since the initial values are \(u_{1}=24\) and \(u_{2}=-54\), we have

    \[\begin{align}u_1&=24=C(4+5i)+D(4-5i)\\ u_2&=-54=C(4+5i)^2+D(4-5i)^2 \end{align}\]

    Solving simultaneously, gives \(C=3\) and \(D=3\).

    Therefore the solution is the closed-form equation,

    $$u_n=3(4+5i)^n+3(4-5i)^n.$$

    Second Order Recurrence Relation - Key takeaways

    • Second-order recurrence relations are ones in which each term of the sequence is a function of the two previous term and are of the form \(u_{n+2}=Au_{n+1}+Bu_{n}+f(n)\) where \(f(n)\) is a polynomial and \(A\) and \(B\) are constants.
    • Second-order recurrence relations are called homogenous if \(f(n)=0\) and non-homogenous otherwise.
    • Solving second-order recurrence relations involves finding the closed-form solution.
    • The method we use to solve these recurrence relations is called the Characteristic Technique and is summarized in the following steps,
      • Step 1. Find the reduced equation by setting \(f(n)=0\).
      • Step 2. Find the characteristic equation and solve for \(r\).
      • Step 3. Find the complementary function.
      • Step 4. Find the particular solution and substitute in \(p(n)=u_{n}\) into the original equation and solve for unknown.
      • Step 5. Now you have a general form for the solution, use the initial values given in the question to find the remaining unknowns.
    Frequently Asked Questions about Second Order Recurrence Relation

    How do you solve second order recurrence relations?

    We can solve second-order recurrence relations using the Characteristic Technique.

    What is the second order recurrence relation used for?

    Second-order recurrence relations are used to model recursive relationships or to iteratively define a sequence.

    What is an example of second order recurrence relation?

    The Fibonacci sequence is an example of a second order recurrence relation that can be written as: Fn = Fn-1 - Fn-2.

    What are the characteristics of second order recurrence relation?

    A second-order recurrence relation is a formula for the nth term in a sequence as a function of the previous two terms. They take the form u= Aun-1 + Aun-2 + f(n), where A and Bare constants, f(n) is a polynomial function of n, and uis the nth term of the sequence. 

    What is degree of recurrence relation? 

    The degree of a recurrence relation is the difference between the highest and lowest index of n. 

    Test your knowledge with multiple choice flashcards

    Which term best describes the following recurrence relation? \(u_{n+2}=2u_{n+1}+3u_n+4n+12\).

    Which term best describes the following recurrence relation? \(u_{n+2}=6u_{n+1}-9u_n\).

    Which term best describes the following recurrence relation? \(u_{n+2}=2u_{n+1}+3u_n+n^2\).

    Next

    Discover learning materials with the free StudySmarter app

    Sign up for free
    1
    About StudySmarter

    StudySmarter is a globally recognized educational technology company, offering a holistic learning platform designed for students of all ages and educational levels. Our platform provides learning support for a wide range of subjects, including STEM, Social Sciences, and Languages and also helps students to successfully master various tests and exams worldwide, such as GCSE, A Level, SAT, ACT, Abitur, and more. We offer an extensive library of learning materials, including interactive flashcards, comprehensive textbook solutions, and detailed explanations. The cutting-edge technology and tools we provide help students create their own learning materials. StudySmarter’s content is not only expert-verified but also regularly updated to ensure accuracy and relevance.

    Learn more
    StudySmarter Editorial Team

    Team Math Teachers

    • 10 minutes reading time
    • Checked by StudySmarter Editorial Team
    Save Explanation Save Explanation

    Study anywhere. Anytime.Across all devices.

    Sign-up for free

    Sign up to highlight and take notes. It’s 100% free.

    Join over 22 million students in learning with our StudySmarter App

    The first learning app that truly has everything you need to ace your exams in one place

    • Flashcards & Quizzes
    • AI Study Assistant
    • Study Planner
    • Mock-Exams
    • Smart Note-Taking
    Join over 22 million students in learning with our StudySmarter App
    Sign up with Email

    Get unlimited access with a free StudySmarter account.

    • Instant access to millions of learning materials.
    • Flashcards, notes, mock-exams, AI tools and more.
    • Everything you need to ace your exams.
    Second Popup Banner