Order 2 Recurrence

Error

There was an error loading the page.

Contributors

Julien Ugon

Feedback

From users who are members of Discrete Mathematics :

Julien Ugon

said

Ready to use

2 years, 7 months ago

History

○

Julien Ugon 2 years, 7 months ago

Published this.

○

Julien Ugon 2 years, 7 months ago

Gave some feedback: Ready to use

○

Julien Ugon 5 years ago

Created this.

Name	Status	Author	Last Modified
Order 2 Recurrence	Ready to use	Julien Ugon	11/04/2025 12:08
Order 2 Recurrence (with steps)	Ready to use	Julien Ugon	09/05/2024 06:04

There are 3 other versions that do you not have access to.

Question statement

Solve the recurrence relation given by:

$\begin{cases} a_0 &= \var{a0}\\ a_1 &= \var{a1}\\ a_n &=\simplify{{recurrence}} \end{cases}$

Give any introductory information the student needs.

			Name	Type	Generated Value

			rootSet	list	List of 20 items
			order	integer	2

			Name	Type	Generated Value

roots	list	[ -1, 5 ]
s1	integer	3
s2	integer	-1

			Name	Type	Generated Value

charac	expression	x^2 - 4x - 5
c1	integer	4
c2	integer	5
closedForm	expression	3*(-1)^n - 5^n
a0	integer	2
a1	integer	-8
recurrence	expression	4sub(a,n - 1) + 5sub(a,n - 2)

			Name	Type	Generated Value

			a2	integer	-22
			a3	integer	-128

			Name	Type	Generated Value

relation	expression	sub(a,n) - (4sub(a,n - 1) + 5sub(a,n - 2))
r2	expression	sub(a,2) - 4sub(a,1) - 5sub(a,0)
x1	integer	-1
x2	integer	5

			Name	Type	Generated Value

test

integer

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
-10..10 except 0

JME function reference

Description

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `list`

[ -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

→ Used by:

roots

This variable doesn't seem to be used anywhere.

Advice

To find the closed form of a linear recurrence of order 2, we have to follow three steps:

Find the characteristic equation.
Solve the characteristic equation to obtain the general form of the sequence.
Find the specific parameters by solving a system of simultaneous equations.

Finding the characteristic equation.

To find the characteristic equation, we first need to rewrite ther recurrence relation to have 0 on the right hand side.

$\begin{align*} a_{n+2} &= \simplify{{recurrence}} \\ \var{relation} &= 0 \end{align*}$

Since this relation must be true for every $n\geq 2$ , it must also apply for $n=2$ :

$\var{r2}=0$

Now, we substitute each $a_{i}$ with $x^i$ , to get the characteristic equation:

$\var{charac}=0$ .

Solving the characteristic equation.

We can solve the characteristic equation using the quadratic formula:

$\frac{-b\pm \sqrt{b^2-4ac}}{2}.$ Here we have

$a=1$ ,

$b=\simplify{-{c1}}$ and

$c=\simplify{-{c2}}$ . So the quadratic formula gives us two solutions to that equation:

$x_1 = \var{roots[0]}$ and

$x_2 = \var{roots[1]}$ . Make sure to verify your intermediate result at this stage by plugging these values back into your equation.

The general form of the sequence is therefore:

$a_n = \simplify{s_1*({x1})^n + s_2*({x2})^n}.$

Finding the parameters $s_1$ and $s_2$ .

To find the parameters $s_1$ and $s_2$ we use the values of the elements $a_0$ and $a_1$ .

For $n=0$ , we know that $a_0=\var{a0}$ , and our general form gives us that this must be equal to $a_0 = s_0*(\var{x1})^0 + s_2*(\var{x2})^0.$
For $n=1$ , we know that $a_1=\var{a1}$ , and our general form gives us that this must be equal to $a_1 = s_1*(\var{x1})^1 + s_2*(\var{x2})^1.$

And so we obtain the simultaneous equations:

$\begin{cases} s_1 + s_2 &= \var{a0}\\ \simplify{+{x1}*s_1 +{x2}*s_2} &= \var{a1} \end{cases}.$

We can solve this system of linear equations, for example by elimination. Let's eliminate $s_2$ :

Multiply the top equation by $\var{x2}$ (the coefficient of $s_2$ in the bottom equation): $\simplify{{x2}*s_1 + {x2}*s_2}=\var{x2*a0}$ .
Subtract the second equation from the first: $\simplify{({x2}-{x1})*s_1} = \var{x2*a0-a1}.$
Solve for $s_1$ using the equation we just obtained: $s_1=\var{s1}$ .
Substitute the value of $s_1$ into the top equation: $s_2=\var{a0}-s_1 = \var{s2}$ .

We find that $s_1 = \var{s1}$ and $s_2=\var{s2}$ . Make sure to verify your intermediate result at this stage by plugging these values back into the two simultaneous equations.

Therefore the closed form is

$a_n = \var{closedForm}.$ Evaluate at least $a_0$ , $a_1$ and $a_2$ with your closed form solution before entering it into the quiz.

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Mathematical expression
Mathematical expression		Hasn't run yet

This question is used in the following exams:

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Julien Ugon 2 years, 7 months ago

Julien Ugon 2 years, 7 months ago

Julien Ugon 5 years ago

Error in variable testing condition

Error

Warning

Generated value: `list`

Parts

Mathematical expression

Advanced settings

Checking accuracy

Variable value generators

Pattern restriction

Variables

String restrictions

Finding the characteristic equation.

Solving the characteristic equation.

Finding the parameters $s_1$ and $s_2$ .

Loading...

Error

Order 2 Recurrence

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Julien Ugon 2 years, 7 months ago

Julien Ugon 2 years, 7 months ago

Julien Ugon 5 years ago

Error in variable testing condition

Error

Warning

Generated value: list

Parts

Mathematical expression

Advanced settings

Checking accuracy

Variable value generators

Pattern restriction

Variables

String restrictions

Finding the characteristic equation.

Solving the characteristic equation.

Finding the parameters s1s_1 and s2s_2.

Generated value: `list`

Finding the parameters $s_1$ and $s_2$ .