Recurrence: first order

Error

There was an error loading the page.

Contributors

Feedback

From users who are members of Discrete Mathematics :

Daniel Mansfield

said

Ready to use

6 years, 2 months ago

History

○

Daniel Mansfield 6 years, 2 months ago

Gave some feedback: Ready to use

○

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.

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 is an equation which can be used to construct a sequence of terms $x_n$ from a given initial value. A first order recurrence relation is of the form

$x_n + Cx_{n-1} = f(n)$

where $C$ is a constant and $f(n)$ is a function of $n$ . When $f(n) = 0$ the recurrence relation is called homogeneous. The concept of a homogeneous recurrence relation is both simple and fundamental.

Give any introductory information the student needs.

			Name	Type	Generated Value

a	integer	2
b	integer	-2
x0	integer	6
x1	integer	10
x2	integer	18
x3	integer	34
x4	integer	66
n0	integer	8
xn0	decimal	dec("1026")

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(2..5)

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`

→ Used by:

This variable doesn't seem to be used anywhere.

Gap-fill

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

Consider the homogeneous first order recurrence relation $x_n - \var{a} x_{n-1}=0$ for $n>0$ with initial condition $x_0 = \var{x0}$ . Re-arrange the relation into the form $x_n = \var{a}x_{n-1}$ to find

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

Advice

The purpose of the first two parts is to present the idea that the solution to a first order recurrence relation is of the form

$x_n = A\times C^n$ .

In this example we explored $x_n - \var{a}x_{n-1} = 0$ , which is a homogeneous equation (because of the zero) and has homogeneous solution

$h_n = \var{x0}\times \var{a}^n$ .

This allows you to calculate the elements in the sequence $x_1 = \var{x0*a}, x_2 = \var{x0*a^2}, x_3 = \var{x0*a^3}$ and $x_4 = \var{x0*a^4}$ .

The rest of the question is about exploring the non-homogeneous recurrence relation $x_n - \var{a}x_{n-1} = \var{b}$ . So you can see the terms of the sequence we begin by iteratively constructing the sequence starting with $x_0 = \var{x0}$ :

$x_1 = \var{a}x_0 + \var{b} = \var{a} \times \var{x0} + \var{b} = \var{x1}$ .

Similarly

$x_2 = \var{a}x_1 + \var{b} = \var{a} \times \var{x1} + \var{b} = \var{x2}$

$x_3 = \var{a}x_2 + \var{b} = \var{a} \times \var{x2} + \var{b} = \var{x3}$

$x_4 = \var{a}x_3 + \var{b} = \var{a} \times \var{x3} + \var{b} = \var{x4}$ .

The solution to the non-homogeneous recurrence relation is of the form $x_n = h_n + p_n$ . So it is always necessary to find the homogeneous solution $h_n$ when solving a (non-homogeneous) recurrence relation. The particular solution in this case is just a constant (since $f(n) = \var{b}$ is also constant, we should expect $p_n$ to also have the same 'shape'). In this case $p_n = \dfrac{\var{b}}{\var{1-a}}=\var{b/(1-a)}$ so the full solution is

$x_n = h_n + p_n = A\times \var{a}^n + \var{b/(1-a)}$ .

Use the initial condition $x_0 = \var{x0}$ to evaluate $A = \var{x0-b/(1-a)}$ .

This solution is very useful to find $x_n$ when $n$ is large. Such as $x_{\var{n0}} = \var{x0 - b/(1-a)}\times \var{a}^\var{n0} + \var{b/(1-a)} = \var{xn0}$ .

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

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 6 years, 2 months ago

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: first order

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Daniel Mansfield 6 years, 2 months ago

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`