// Numbas version: exam_results_page_options {"name": "Recurrence: second order", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Recurrence: second order", "tags": [], "metadata": {"description": "

How to find solutions to a second order recurrence relation.

", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "

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

\n

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

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

\n

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.

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

\n

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

\n

Similarly

\n

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

\n

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

\n

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

\n
\n

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

\n

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

\n

The first step is to solve the homogeneous equation

\n

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

\n

The solution to the homogeneous equation is:

\n

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

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

\n

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

\n

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

\n

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

\n

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

\n

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

", "rulesets": {}, "extensions": [], "variables": {"c1": {"name": "c1", "group": "Ungrouped variables", "definition": "(lambda1+lambda2)", "description": "", "templateType": "anything"}, "lambda1": {"name": "lambda1", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "templateType": "anything"}, "_b": {"name": "_b", "group": "Ungrouped variables", "definition": "random(-2..2)", "description": "", "templateType": "anything"}, "B": {"name": "B", "group": "Ungrouped variables", "definition": "random(-5..5 except [lambda1,lambda2,A,0])", "description": "", "templateType": "anything"}, "x1": {"name": "x1", "group": "Ungrouped variables", "definition": "A*lambda1 + B*lambda2+_a+_b", "description": "", "templateType": "anything"}, "lambda2": {"name": "lambda2", "group": "Ungrouped variables", "definition": "random(1..5 except lambda1)", "description": "", "templateType": "anything"}, "polya": {"name": "polya", "group": "Ungrouped variables", "definition": "_a*(1-c1+c2)", "description": "", "templateType": "anything"}, "x2": {"name": "x2", "group": "Ungrouped variables", "definition": "c1*x1-c2*x0", "description": "", "templateType": "anything"}, "x3": {"name": "x3", "group": "Ungrouped variables", "definition": "c1*x2-c2*x1", "description": "", "templateType": "anything"}, "A": {"name": "A", "group": "Ungrouped variables", "definition": "random(-5..5 except [lambda1,lambda2,0])", "description": "", "templateType": "anything"}, "x5": {"name": "x5", "group": "Ungrouped variables", "definition": "c1*x4-c2*x3", "description": "", "templateType": "anything"}, "x4": {"name": "x4", "group": "Ungrouped variables", "definition": "c1*x3-c2*x2", "description": "", "templateType": "anything"}, "x0": {"name": "x0", "group": "Ungrouped variables", "definition": "A+B+_b", "description": "", "templateType": "anything"}, "_a": {"name": "_a", "group": "Ungrouped variables", "definition": "random(2..3)", "description": "", "templateType": "anything"}, "polyb": {"name": "polyb", "group": "Ungrouped variables", "definition": "_b*(1-c1+c2)+_a*(c1-2c2)", "description": "", "templateType": "anything"}, "c2": {"name": "c2", "group": "Ungrouped variables", "definition": "lambda1*lambda2", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "not (polya = 0)", "maxRuns": 100}, "ungrouped_variables": ["c1", "c2", "x0", "x1", "x2", "x3", "x4", "x5", "lambda1", "lambda2", "A", "B", "polya", "_a", "polyb", "_b"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

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

\n
\n
• $x_2 =$ [[0]]
• \n
• $x_3 =$ [[1]]
• \n
• $x_4 =$ [[2]]
• \n
• $x_5 =$ [[3]].
• \n

The $n$th term of a second order homogeneous recurrence relation can be expressed in the form

\n

$h_n = A\\lambda_1^n + B\\lambda_2^n$

\n

This is also called the homogeneous solution. Using the same recurrence relation $x_n - \\var{c1} x_{n-1} + \\var{c2}x_{n-2}=0$, what are the values for $\\lambda_1$ and $\\lambda_2$? Give your answer as a set of numbers using the NUMBAS syntax set() for set.

", "stepsPenalty": 0, "steps": [{"type": "information", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

Suppose that $\\lambda^n$ is a solution to the recurrence relation (and ignore the trivial case where $\\lambda = 0$). Then

\n

$\\lambda^n - \\var{c1} \\lambda^{n-1} + \\var{c2}\\lambda^{n-2}=0$.

\n

Since $\\lambda \\neq 0$, this reduces to

\n

$\\lambda^2 - \\var{c1} \\lambda + \\var{c2}=0$.

\n

The solutions to this equation are the values of $\\lambda_1$ and $\\lambda_2$.

"}], "answer": "{set(lambda1,lambda2)}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": "6", "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

The $n$th term of a second order non-homogeneous recurrence relation can be expressed in the form

\n

$x_n = h_n + p_n$

\n

where $h_n$ is the homogeneous solution, and $p_n$ is a particular non-homogeneous solution. The sum of the homogeneous and particular solutions is the general solution to the non-homogeneous recurrence relation.

\n

Find the solution to the non-homogeneous second order recurrence relation

\n

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

\n

with initial conditions $x_0 = \\var{x0}$ and $x_1 = \\var{x1}$.

", "stepsPenalty": 0, "steps": [{"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

Again, there is no simple guaranteed method to find $p_n$, and so we must 'guess and check'. Suppose $p_n$ is a particular solution to the non-homogeneous equation:

\n

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

\n

Since the non-homogeneous part $f(n) = \\simplify{{polya}*n+{polyb}}$ is a degree one (linear) polynomial, we 'guess' that $p_n = an+b$ for some constants $a$ and $b$:

\n

$(an+b) - \\var{c1} (a(n-1)+b) + \\var{c2}(a(n-2)+b) =\\simplify{{polya}*n+{polyb}}$.

\n

This can be simplified to find the values of $a$ and $b$. The value of $a$ is

", "answer": "{_a}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

The value of $b$ is

", "answer": "{_b}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": "1", "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

The final step is to apply the initial conditions and discover the values of $A$ and $B$. When $n=0$:

\n

$\\var{x0} = h_0 + p_0 = A+B+b$

\n

and when $n=1$:

\n

$\\var{x1} = h_1 + p_1 = A\\lambda_1+B\\lambda_2 + a+b$

\n

These equations can be solved simultaneously to find the values of $A$ and $B$.

\n

Picking $\\lambda_1 = \\var{lambda1}$ and $\\lambda_2 = \\var{lambda2}$, the value of $A$ is

", "answer": "{A}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

The value of $B$ is

", "answer": "{B}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": []}, {"type": "information", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "

\n

$x_n = A\\lambda_1^n + B\\lambda_2^n + an +b$

\n

where $a,b,\\lambda_1,\\lambda_2,A$ and $B$ have the values determined above.

"}], "answer": "{A}*{lambda1}^n + {B}*{lambda2}^n+{_a}*n+{_b}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": [{"name": "n", "value": ""}]}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}]}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}