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)$
\nwhere $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.
\nWhen $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.
", "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
\n$x_2 = \\var{c1}x_1 - \\var{c2}x_0 = \\var{c1} \\times \\var{x1} - \\var{c2} \\times \\var{x0} = \\var{x2}$.
\nSimilarly
\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}$.
\nThe 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}}$.
\nThe first step is to solve the homogeneous equation
\n$x_n - \\var{c1} x_{n-1} + \\var{c2}x_{n-2}=0$.
\nThe solution to the homogeneous equation is:
\n$h_n = A\\var{lambda1}^n + B\\var{lambda2}^n$
\nwhere 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.
\nTo 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}}$.
\nBy 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}}$.
\nThe 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": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"c1": {"name": "c1", "group": "Ungrouped variables", "definition": "(lambda1+lambda2)", "description": "", "templateType": "anything", "can_override": false}, "lambda1": {"name": "lambda1", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "_b": {"name": "_b", "group": "Ungrouped variables", "definition": "random(-2..2)", "description": "", "templateType": "anything", "can_override": false}, "B": {"name": "B", "group": "Ungrouped variables", "definition": "random(-5..5 except [lambda1,lambda2,A,0])", "description": "", "templateType": "anything", "can_override": false}, "x1": {"name": "x1", "group": "Ungrouped variables", "definition": "A*lambda1 + B*lambda2+_a+_b", "description": "", "templateType": "anything", "can_override": false}, "lambda2": {"name": "lambda2", "group": "Ungrouped variables", "definition": "random(1..5 except lambda1)", "description": "", "templateType": "anything", "can_override": false}, "polya": {"name": "polya", "group": "Ungrouped variables", "definition": "_a*(1-c1+c2)", "description": "", "templateType": "anything", "can_override": false}, "x2": {"name": "x2", "group": "Ungrouped variables", "definition": "c1*x1-c2*x0", "description": "", "templateType": "anything", "can_override": false}, "x3": {"name": "x3", "group": "Ungrouped variables", "definition": "c1*x2-c2*x1", "description": "", "templateType": "anything", "can_override": false}, "A": {"name": "A", "group": "Ungrouped variables", "definition": "random(-5..5 except [lambda1,lambda2,0])", "description": "", "templateType": "anything", "can_override": false}, "x5": {"name": "x5", "group": "Ungrouped variables", "definition": "c1*x4-c2*x3", "description": "", "templateType": "anything", "can_override": false}, "x4": {"name": "x4", "group": "Ungrouped variables", "definition": "c1*x3-c2*x2", "description": "", "templateType": "anything", "can_override": false}, "x0": {"name": "x0", "group": "Ungrouped variables", "definition": "A+B+_b", "description": "", "templateType": "anything", "can_override": false}, "_a": {"name": "_a", "group": "Ungrouped variables", "definition": "random(2..3)", "description": "", "templateType": "anything", "can_override": false}, "polyb": {"name": "polyb", "group": "Ungrouped variables", "definition": "_b*(1-c1+c2)+_a*(c1-2c2)", "description": "", "templateType": "anything", "can_override": false}, "c2": {"name": "c2", "group": "Ungrouped variables", "definition": "lambda1*lambda2", "description": "", "templateType": "anything", "can_override": false}}, "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, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "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
\nThe $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$
\nThis 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.
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$.
\nSince $\\lambda \\neq 0$, this reduces to
\n$\\lambda^2 - \\var{c1} \\lambda + \\var{c2}=0$.
\nThe 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, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": "6", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "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$
\nwhere $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.
\nFind 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}}$
\nwith initial conditions $x_0 = \\var{x0}$ and $x_1 = \\var{x1}$.
", "stepsPenalty": 0, "steps": [{"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "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}}$.
\nSince 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}}$.
\nThis 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, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "The value of $b$ is
", "answer": "{_b}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": "1", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "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$
\nand when $n=1$:
\n$\\var{x1} = h_1 + p_1 = A\\lambda_1+B\\lambda_2 + a+b$
\nThese equations can be solved simultaneously to find the values of $A$ and $B$.
\nPicking $\\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, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "The value of $B$ is
", "answer": "{B}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "information", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "The answer is then
\n$x_n = A\\lambda_1^n + B\\lambda_2^n + an +b$
\nwhere $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, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": [{"name": "n", "value": ""}]}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "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/"}]}