Recurrence: second order

Error

There was an error loading the page.

Contributors

Feedback

From users who are members of Discrete Mathematics :

Daniel Mansfield

said

Needs to be tested

7 years, 6 months ago

History

○

Daniel Mansfield 7 years, 6 months ago

Published this.

○

Daniel Mansfield 7 years, 6 months ago

Gave some feedback: Needs to be tested

○

Daniel Mansfield 7 years, 6 months ago

Created this as a copy of Recurrence: first order.

Name	Status	Author	Last Modified
Recurrence: first order	Ready to use	Daniel Mansfield	13/02/2020 02:01
Recurrence: second order	Needs to be tested	Daniel Mansfield	08/04/2022 08:35

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

Question statement

A recurrence relation of order $k$ is of the form

$x_n + c_1x_{n-1} + \cdots c_kx_{n-k}= f(n)$

where $c_1, \cdots c_k$ are constants and $f(n)$ is a function of $n$ . To fully determine the solution, a recurrence relation of order $k$ must also have $k$ initial conditions.

When $k=1$ this is a first order recurrence relation, which we explored in the previous online tutorial. When $k=2$ this is called a second order recurrence relation.

Give any introductory information the student needs.

			Name	Type	Generated Value

c1	integer	7
c2	integer	12
x0	integer	7
x1	integer	25
x2	integer	91
x3	integer	337
x4	integer	1267
x5	integer	4825
lambda1	integer	4
lambda2	integer	3
A	integer	2
B	integer	5
polya	integer	12
_a	integer	2
polyb	integer	-34
_b	integer	0

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
(lambda1+lambda2)

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: `integer`

← Depends on:

This variable doesn't seem to be used anywhere.

Parts

Part a) Gap-fill
Part b) Mathematical expression
1. Step Information only
Part c) Mathematical expression

Gap-fill

Ask the student a question, and give any hints about how they should answer this part.

Consider the homogeneous second order recurrence relation $x_n - \var{c1} x_{n-1} + \var{c2}x_{n-2}=0$ for $n>1$ with initial conditions $x_0 = \var{x0}$ and $x_1 = \var{x1}$ . Re-arrange the relation into the form $x_n = \var{c1} x_{n-1} - \var{c2}x_{n-2}$ to find

$x_2 =$ Gap 0.
$x_3 =$ Gap 1.
$x_4 =$ Gap 2.
$x_5 =$ Gap 3..

Advice

The first part of this question is about exploring a second order recurrence relation. Starting with the initial conditions $x_0 = \var{x0}$ and $x_1 = \var{x1}$ , you use the recurrence relation to find

$x_2 = \var{c1}x_1 - \var{c2}x_0 = \var{c1} \times \var{x1} - \var{c2} \times \var{x0} = \var{x2}$ .

Similarly

$x_3 = \var{c1}x_2 - \var{c2}x_1 = \var{x3}$

$x_4 = \var{c1}x_3 - \var{c2}x_2 = \var{x4}$

$x_5 = \var{c1}x_4 - \var{c2}x_3 = \var{x5}$ .

The rest of the question is dedicated to the method of solving a second order recurrence relation

$x_n - \var{c1} x_{n-1} + \var{c2}x_{n-2}=\simplify{{polya} n + {polyb}}$ .

The first step is to solve the homogeneous equation

$x_n - \var{c1} x_{n-1} + \var{c2}x_{n-2}=0$ .

The solution to the homogeneous equation is:

$h_n = A\var{lambda1}^n + B\var{lambda2}^n$

where the values $\var{lambda1}$ and $\var{lambda2}$ are the solutions to the characteristic equation $\lambda^2 - \var{c1}\lambda + \var{c2} = 0$ . Only evaluate the constants $A$ and $B$ in the final step.

To find the particular solution $p_n$ we 'guess' that $p_n = an+b$ is a solution, so

$p_n - \var{c1} p_{n-1} + \var{c2}p_{n-2}=\simplify{{polya} n + {polyb}}$ .

By comparing coefficients of $n^1$ and $n^0$ (or otherwise) it can be determined that $p_n = \simplify{{_a} n+{_b}}$ . The general solution is then

$h_n + p_n = A \times \var{lambda1}^n + B\times\var{lambda2}^n + \simplify{{_a} n+{_b}}$ .

The values $A=\var{A}$ and $B=\var{B}$ are determined by the initial conditions $x_0=h_0+p_0$ and $x_1 = h_1+p_1$ .

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?
Gap-fill
Gap-fill		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Information only
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Information only

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

Daniel Mansfield 7 years, 6 months ago

Daniel Mansfield 7 years, 6 months ago

Daniel Mansfield 7 years, 6 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

Loading...

Error

Recurrence: second order

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Daniel Mansfield 7 years, 6 months ago

Daniel Mansfield 7 years, 6 months ago

Daniel Mansfield 7 years, 6 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

Generated value: `integer`