// Numbas version: finer_feedback_settings {"name": "Order 2 Recurrence (with steps)", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Order 2 Recurrence (with steps)", "tags": [], "metadata": {"description": "
In this question the students have to solve a linear recurrence of order 2. The sequence is asked in recurrence form and the goal is to find its closed form.
", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "Solve the recurrence relation given by: \\begin{cases} a_0 &= \\var{a0}\\\\ a_1 &= \\var{a1}\\\\ a_n &=\\simplify{{recurrence}} \\end{cases}
", "advice": "To find the closed form of a linear recurrence of order 2, we have to follow three steps:
\nTo find the characteristic equation, we first need to rewrite ther recurrence relation to have 0 on the right hand side.
\n\\[\\begin{align*} a_{n+2} &= \\simplify{{recurrence}} \\\\ \\var{relation} &= 0 \\end{align*}\\]
\nSince this relation must be true for every \\(n\\geq 2\\), it must also apply for \\(n=2\\): \\[\\var{r2}=0\\]
\nNow, we substitute each \\(a_{i}\\) with \\(x^i\\), to get the characteristic equation: \\[\\var{charac}=0\\].
\nWe can solve the characteristic equation using the quadratic formula: \\[\\frac{-b\\pm \\sqrt{b^2-4ac}}{2}.\\] Here we have \\(a=1\\), \\(b=\\simplify{-{c1}}\\) and \\(c=\\simplify{-{c2}}\\). So the quadratic formula gives us two solutions to that equation: \\(x_1 = \\var{roots[0]}\\) and \\(x_2 = \\var{roots[1]}\\). Make sure to verify your intermediate result at this stage by plugging these values back into your equation.
\nThe general form of the sequence is therefore: \\[a_n = \\simplify{s_1*({x1})^n + s_2*({x2})^n}.\\]
\nTo find the parameters \\(s_1\\) and \\(s_2\\) we use the values of the elements \\(a_0\\) and \\(a_1\\).
\nAnd so we obtain the simultaneous equations: \\[ \\begin{cases} s_1 + s_2 &= \\var{a0}\\\\ \\simplify{+{x1}*s_1 +{x2}*s_2} &= \\var{a1} \\end{cases}. \\]
\nWe can solve this system of linear equations, for example by elimination. Let's eliminate $s_2$:
\nWe find that \\(s_1 = \\var{s1}\\) and \\(s_2=\\var{s2}\\). Make sure to verify your intermediate result at this stage by plugging these values back into the two simultaneous equations.
\nTherefore the closed form is \\[a_n = \\var{closedForm}.\\] Evaluate at least \\(a_0\\), \\(a_1\\) and \\(a_2\\) with your closed form solution before entering it into the quiz.
", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"rootSet": {"name": "rootSet", "group": "Parameters", "definition": "-10..10 except 0", "description": "", "templateType": "anything", "can_override": false}, "order": {"name": "order", "group": "Parameters", "definition": "2", "description": "", "templateType": "anything", "can_override": false}, "roots": {"name": "roots", "group": "Randomised parameters", "definition": "shuffle(rootSet)[0..order]", "description": "", "templateType": "anything", "can_override": false}, "charac": {"name": "charac", "group": "Generated Values", "definition": "simplify(expression(\"(x-{roots[0]})*(x-{roots[1]})\"),[\"all\",\"expandbrackets\"])", "description": "", "templateType": "anything", "can_override": false}, "c1": {"name": "c1", "group": "Generated Values", "definition": "roots[0]+roots[1]", "description": "", "templateType": "anything", "can_override": false}, "c2": {"name": "c2", "group": "Generated Values", "definition": "-roots[0]*roots[1]", "description": "", "templateType": "anything", "can_override": false}, "closedForm": {"name": "closedForm", "group": "Generated Values", "definition": "simplify(expression(\"{s1}*({roots[0]})^n+{s2}*({roots[1]})^n\"),[\"all\"])", "description": "", "templateType": "anything", "can_override": false}, "s2": {"name": "s2", "group": "Randomised parameters", "definition": "coefs[indices(roots,x2)[0]]", "description": "", "templateType": "anything", "can_override": false}, "s1": {"name": "s1", "group": "Randomised parameters", "definition": "coefs[indices(roots,x1)[0]]", "description": "", "templateType": "anything", "can_override": false}, "a0": {"name": "a0", "group": "Generated Values", "definition": "s1+s2", "description": "", "templateType": "anything", "can_override": false}, "a1": {"name": "a1", "group": "Generated Values", "definition": "s1*roots[0]+s2*roots[1]", "description": "", "templateType": "anything", "can_override": false}, "recurrence": {"name": "recurrence", "group": "Generated Values", "definition": "simplify(expression(\"{c1}*sub(a,n-1)+{c2}*sub(a,n-2)\"),[\"all\"])", "description": "", "templateType": "anything", "can_override": false}, "a2": {"name": "a2", "group": "Feedback", "definition": "c1*a1+c2*a0", "description": "", "templateType": "anything", "can_override": false}, "a3": {"name": "a3", "group": "Feedback", "definition": "c1*a2+c2*a1", "description": "", "templateType": "anything", "can_override": false}, "relation": {"name": "relation", "group": "Advice", "definition": "simplify(expression(\"sub(a,n) - ({recurrence})\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "r2": {"name": "r2", "group": "Advice", "definition": "simplify(expression(\"sub(a,2)-{c1}*sub(a,1)-{c2}*sub(a,0)\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "test": {"name": "test", "group": "Ungrouped variables", "definition": "random(1,2)", "description": "", "templateType": "anything", "can_override": false}, "x1": {"name": "x1", "group": "Advice", "definition": "roots[0]", "description": "", "templateType": "anything", "can_override": false}, "x2": {"name": "x2", "group": "Advice", "definition": "roots[1]", "description": "", "templateType": "anything", "can_override": false}, "rootind": {"name": "rootind", "group": "Feedback", "definition": "indices(roots,x1)[0]", "description": "", "templateType": "anything", "can_override": false}, "genform": {"name": "genform", "group": "Feedback", "definition": "simplify(expression(\"s_1*({x1})^n + s_2*({x2})^n\"),['all'])", "description": "", "templateType": "anything", "can_override": false}, "lin": {"name": "lin", "group": "Feedback", "definition": "map(simplify(substitute(['n':k],genform),['all']),k,[1,2])", "description": "", "templateType": "anything", "can_override": false}, "lineareqns": {"name": "lineareqns", "group": "Feedback", "definition": "map(expression(\"{lin[k]}={a[k]}\"),k,[0,1])", "description": "", "templateType": "anything", "can_override": false}, "a": {"name": "a", "group": "Feedback", "definition": "map(eval(closedform,['n':k]),k,0..5)", "description": "", "templateType": "anything", "can_override": false}, "coefs": {"name": "coefs", "group": "Randomised parameters", "definition": "[random(-3..3 except 0), random(-5..5 except 0)]", "description": "", "templateType": "anything", "can_override": false}, "t1": {"name": "t1", "group": "Generated Values", "definition": "a[0]-s1", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "not (roots[0] = -roots[1])", "maxRuns": 100}, "ungrouped_variables": ["test"], "variable_groups": [{"name": "Parameters", "variables": ["rootSet", "order"]}, {"name": "Randomised parameters", "variables": ["roots", "coefs", "s1", "s2"]}, {"name": "Generated Values", "variables": ["charac", "c1", "c2", "closedForm", "a0", "a1", "recurrence", "t1"]}, {"name": "Feedback", "variables": ["a", "a2", "a3", "rootind", "genform", "lin", "lineareqns"]}, {"name": "Advice", "variables": ["relation", "r2", "x1", "x2"]}], "functions": {"subvalue": {"parameters": [["ex", "expression"], ["k", "number"]], "type": "expression", "language": "jme", "definition": "substitute([\"n\":k],ex)"}}, "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": "Note the index! $a_n =$[[0]]
", "stepsPenalty": 0, "steps": [{"type": "information", "useCustomName": true, "customName": "Step 1", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "The first step is to find the characteristic polynomial of the sequence. Suppose that $a_n=x^n$ and substitute into the recurrence equation. By taking $n=2$ you should get a quadratic equation. The quadratic polynomial is the characteristic equation of this sequence.
"}, {"type": "jme", "useCustomName": true, "customName": "Characteristic Polynomial", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "What is the characteristic polynomial of this recurrence equation?
", "answer": "{charac}", "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": true, "customName": "Step 2", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "The second step is to solve the quadratic equation by finding the roots of the polynomial.
"}, {"type": "numberentry", "useCustomName": true, "customName": "x\u2081", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "numberInRange (Is the student's number in the allowed range?):\n if(studentNumber=roots[0] or studentNumber=roots[1],\n correct()\n ,\n incorrect();\n end()\n )", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Enter the first root of the characteristic polynomial.
", "minValue": "roots[0]", "maxValue": "roots[0]", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "x\u2082", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [{"variable": "x1", "part": "p0s3", "must_go_first": true}], "variableReplacementStrategy": "alwaysreplace", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Enter the second root of the characteristic polynomial.
", "minValue": "roots[1-indices(roots,roots[rootind])[0]]", "maxValue": "roots[1-indices(roots,roots[rootind])[0]]", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "information", "useCustomName": true, "customName": "Step 3", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Now you should have the general form of the sequence, which should be $a_n = s_1 x_1^n + s_2 x_2^n$, where $x_1$ and $x_2$ are the roots of the equation that you just solved, and $s_1$ and $s_2$ are numbers that we will find later.
"}, {"type": "jme", "useCustomName": true, "customName": "General Form", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [{"variable": "x1", "part": "p0s3", "must_go_first": true}, {"variable": "x2", "part": "p0s4", "must_go_first": true}], "variableReplacementStrategy": "alwaysreplace", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Enter the general form of this equation: $a_n=$
", "answer": "{genform}", "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": true, "customName": "Step 4", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "The last step is to find $s_1$ and $s_2$ using the first two elements of the sequence, $a_0$ and $a_1$.
"}, {"type": "jme", "useCustomName": true, "customName": "Linear equation for n=0", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [{"variable": "x1", "part": "p0s3", "must_go_first": false}, {"variable": "x2", "part": "p0s4", "must_go_first": false}], "variableReplacementStrategy": "alwaysreplace", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Using the general expression for $a_n$ above with $n=0$, find the first equation of your simultaneous system of equations.
", "answer": "s_1+s_2={a[0]}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": "15", "vsetRange": ["0", "1"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": [{"name": "s_1", "value": "random(random(vRange),a[0]-s_2)"}, {"name": "s_2", "value": ""}]}, {"type": "jme", "useCustomName": true, "customName": "Linear equation for n=1", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [{"variable": "x1", "part": "p0s3", "must_go_first": true}, {"variable": "x2", "part": "p0s4", "must_go_first": true}], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Using the general expression for $a_n$ above with $n=1$, find the first equation of your simultaneous system of equations.
", "answer": "{x1}*s_1+{x2}*s_2={a[1]}", "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": "s_1", "value": "random(random(vRange),(a[1]-{x2}*s_2)/{x1})"}, {"name": "s_2", "value": ""}]}, {"type": "information", "useCustomName": true, "customName": "Step 5", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Now you can solve this system of simultaneous equations to find the values of $s_1$ and $s_2$.
"}, {"type": "numberentry", "useCustomName": true, "customName": "s\u2081", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [{"variable": "x1", "part": "p0s3", "must_go_first": true}, {"variable": "x2", "part": "p0s4", "must_go_first": true}], "variableReplacementStrategy": "alwaysreplace", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "$s_1=$
", "minValue": "s1", "maxValue": "s1", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": true, "customName": "s\u2082", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [{"variable": "x1", "part": "p0s3", "must_go_first": true}, {"variable": "x2", "part": "p0s4", "must_go_first": true}], "variableReplacementStrategy": "alwaysreplace", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "$s_2=$
", "minValue": "s2", "maxValue": "s2", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "information", "useCustomName": true, "customName": "Final Step", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "You can now substitute $s_1$, $s_2$, $x_1$ and $x_2$ in the general equation, to obtain the closed form of the sequence $a_n$.
"}], "gaps": [{"type": "jme", "useCustomName": true, "customName": "a\u2099", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "azero (check that the student's answer is correct for n=0):\n assert(resultsequal(unset(question_definitions,eval(studentCompare,['n':0])),unset(question_definitions,eval(correctCompare,['n':0])),settings[\"checkingType\"],settings[\"checkingAccuracy\"]),\n negative_feedback(render(safe(\"Your formula fails for $n=0$. We expect that $a_0=\\\\var{a0}$, but with your formula we get $a_0=\\\\var{nex}=\\\\var{nv}$.
It is likely that you made a mistake while solving the linear system, at the and. You could have caught this mistake by plugging the values back into the equations before entering them into Numbas.
\"),[\"nex\":subvalue(studentCompare,0),\"nv\":eval(studentCompare,['n':0])])))\n\n\naone (check that the student's answer is correct for n=0):\n assert(resultsequal(unset(question_definitions,eval(studentCompare,['n':1])),unset(question_definitions,eval(correctCompare,['n':1])),settings[\"checkingType\"],settings[\"checkingAccuracy\"]),\n negative_feedback(render(safe(\"Your formula fails for n=1. We expect that $a_1=\\\\var{a1}$, but with your formula we get $a_1=\\\\var{nex}=\\\\var{nv}$.
It is likely that you made a mistake while solving the linear system, at the and. You could have caught this mistake by plugging the values back into the equations before entering them into Numbas.
\"),[\"nex\":subvalue(studentCompare,1),\"nv\":eval(studentCompare,['n':1])])))\n\natwo (check that the student's answer is correct for n=2):\n assert(resultsequal(unset(question_definitions,eval(studentCompare,['n':2])),unset(question_definitions,eval(correctCompare,['n':2])),settings[\"checkingType\"],settings[\"checkingAccuracy\"]),\n negative_feedback(render(safe(\"Your formula fails for n=2. We expect that $a_2=\\\\var{a2}$, but with your formula we get $a_2=\\\\var{nex}=\\\\var{nv}$.
It seems that you made a mistake when solving the quadratic equation, or when finding the characteristic polynomial. You probably could have caught the mistake by plugging the values into the equation.
\"),[\"nex\":subvalue(studentCompare,2),\"nv\":eval(studentCompare,['n':2])])))\n\nmark:\n apply(studentExpr);\n apply(failNameToCompare);\n apply(unexpectedVariables);\n apply(sameVars);\n apply(azero);\n apply(aone);\n apply(atwo);\n apply(numericallyCorrect);\n apply(failMinLength);\n apply(failMaxLength);\n apply(forbiddenStringsPenalty);\n apply(requiredStringsPenalty);\n apply(failMatchPattern)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "{closedForm}", "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": []}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}]}], "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}