Introduction to first order recurrence relations with a simple example, including homogenous and non-homogenous solutions.
", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "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
\n$x_n + Cx_{n-1} = f(n)$
\nwhere $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.
", "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
\n$x_n = A\\times C^n$.
\nIn 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
\n$h_n = \\var{x0}\\times \\var{a}^n$.
\nThis 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}$.
\nThe 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}$:
\n$x_1 = \\var{a}x_0 + \\var{b} = \\var{a} \\times \\var{x0} + \\var{b} = \\var{x1}$.
\nSimilarly
\n$x_2 = \\var{a}x_1 + \\var{b} = \\var{a} \\times \\var{x1} + \\var{b} = \\var{x2}$
\n$x_3 = \\var{a}x_2 + \\var{b} = \\var{a} \\times \\var{x2} + \\var{b} = \\var{x3}$
\n$x_4 = \\var{a}x_3 + \\var{b} = \\var{a} \\times \\var{x3} + \\var{b} = \\var{x4}$.
\nThe 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
\n$x_n = h_n + p_n = A\\times \\var{a}^n + \\var{b/(1-a)}$.
\nUse the initial condition $x_0 = \\var{x0}$ to evaluate $A = \\var{x0-b/(1-a)}$.
\nThis 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}$.
", "rulesets": {}, "extensions": [], "variables": {"b": {"name": "b", "group": "Ungrouped variables", "definition": "random(1..6)*(1-a)", "description": "", "templateType": "anything"}, "x4": {"name": "x4", "group": "Ungrouped variables", "definition": "a*x3+b", "description": "", "templateType": "anything"}, "xn0": {"name": "xn0", "group": "Ungrouped variables", "definition": "(x0-b/(1-a))*(a^n0) + b/(1-a)", "description": "", "templateType": "anything"}, "x0": {"name": "x0", "group": "Ungrouped variables", "definition": "random(2..9 except [a,b,b/(1-a)])", "description": "", "templateType": "anything"}, "x3": {"name": "x3", "group": "Ungrouped variables", "definition": "a*x2+b", "description": "", "templateType": "anything"}, "n0": {"name": "n0", "group": "Ungrouped variables", "definition": "random(6..9)", "description": "", "templateType": "anything"}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "random(2..5)", "description": "", "templateType": "anything"}, "x2": {"name": "x2", "group": "Ungrouped variables", "definition": "a*x1+b", "description": "", "templateType": "anything"}, "x1": {"name": "x1", "group": "Ungrouped variables", "definition": "(a*x0 + b)", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["a", "b", "x0", "x1", "x2", "x3", "x4", "n0", "xn0"], "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 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
\nThe $n$th term of a first order homogeneous recurrence relation can be expressed in the form
\n$h_n = A\\times C^n$
\nwhere $C$ is determined by the coefficients, and $A$ is determined by the initial conditions. This is also called the homogeneous solution. What is the value of $C$ in the homogeneous solution for the above sequence?
", "answer": "{a}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": []}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "Consider the non-homogeneous first order recurrence relation $x_n - \\var{a} x_{n-1} = \\var{b}$ for $n>0$ with initial condition $x_0 = \\var{x0}$. Re-arrange the relation into the form $x_n = \\var{a}x_{n - 1} - \\var{-1*b}$ to find
\nThe $n$th term of a first 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. Find the (general) solution to $x_n - \\var{a}x_{n-1} = \\var{b}$ subject to the initial condition $x_0 = \\var{x0}$.
", "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": "There is no simple guaranteed method to finding $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{a} p_{n-1} = \\var{b}$.
\nSince the non-homogeneous part $f(n) = \\var{b}$ is constant, we 'guess' that $p_n = D$ for some constant $D$:
\n$D - \\var{a} D = \\var{b}$.
\nThis guess must have worked since the above equation is solvable, and the value of $D$ is:
", "answer": "{b/(1-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 general solution is therefore $h_n + D$ where $h_n$ and $D$ are determined above. Now apply the initial condition
\n$\\var{x0} = x_0 = h_0 + p_0=A\\var{a}^0+D=A+D$
\nto determine the value of $A$, which is:
", "answer": "{x0-b/(1-a)}", "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": "The complete solution is therefore $h_n + p_n = A\\times \\var{a}^n + D$ where $A$ and $D$ have the values determined above.
"}], "answer": "{x0-b/(1-a)}*{a}^n + {b/(1-a)}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "Use your solution to evaluate $x_{\\var{n0}}$.
", "answer": "{xn0}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "valuegenerators": []}], "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/"}], "resources": []}]}], "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/"}]}