// Numbas version: finer_feedback_settings
{"name": "Order 2 Recurrence", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Order 2 Recurrence", "tags": [], "metadata": {"description": "<p>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.</p>", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "<p>Solve the recurrence relation given by: \\begin{cases} a_0 &amp;= \\var{a0}\\\\ a_1 &amp;= \\var{a1}\\\\ a_n &amp;=\\simplify{{recurrence}} \\end{cases}</p>", "advice": "<p>To find the closed form of a linear recurrence of order 2, we have to follow three steps:</p>\n<ol type=\"1\">\n<li>Find the characteristic equation.</li>\n<li>Solve the characteristic equation to obtain the general form of the sequence.</li>\n<li>Find the specific parameters by solving a system of simultaneous equations.</li>\n</ol>\n<h2 id=\"finding-the-characteristic-equation.\">Finding the characteristic equation.</h2>\n<p>To find the characteristic equation, we first need to rewrite ther recurrence relation to have 0 on the right hand side.</p>\n<p><span class=\"math display\">\\[\\begin{align*} a_{n+2} &amp;= \\simplify{{recurrence}} \\\\ \\var{relation} &amp;= 0 \\end{align*}\\]</span></p>\n<p>Since this relation must be true for every <span class=\"math inline\">\\(n\\geq 2\\)</span>, it must also apply for <span class=\"math inline\">\\(n=2\\)</span>: <span class=\"math display\">\\[\\var{r2}=0\\]</span></p>\n<p>Now, we substitute each <span class=\"math inline\">\\(a_{i}\\)</span> with <span class=\"math inline\">\\(x^i\\)</span>, to get the characteristic equation: <span class=\"math display\">\\[\\var{charac}=0\\]</span>.</p>\n<h2 id=\"solving-the-characteristic-equation.\">Solving the characteristic equation.</h2>\n<p>We can solve the characteristic equation using the quadratic formula: <span class=\"math display\">\\[\\frac{-b\\pm \\sqrt{b^2-4ac}}{2}.\\]</span> Here we have <span class=\"math inline\">\\(a=1\\)</span>, <span class=\"math inline\">\\(b=\\simplify{-{c1}}\\)</span> and <span class=\"math inline\">\\(c=\\simplify{-{c2}}\\)</span>. So the quadratic formula gives us two solutions to that equation: <span class=\"math inline\">\\(x_1 = \\var{roots[0]}\\)</span> and <span class=\"math inline\">\\(x_2 = \\var{roots[1]}\\)</span>. <strong>Make sure to verify your intermediate result at this stage by plugging these values back into your equation.</strong></p>\n<p>The general form of the sequence is therefore: <span class=\"math display\">\\[a_n = \\simplify{s_1*({x1})^n + s_2*({x2})^n}.\\]</span></p>\n<h2 id=\"finding-the-parameters-s_1-and-s_2.\">Finding the parameters <span class=\"math inline\">\\(s_1\\)</span> and <span class=\"math inline\">\\(s_2\\)</span>.</h2>\n<p>To find the parameters <span class=\"math inline\">\\(s_1\\)</span> and <span class=\"math inline\">\\(s_2\\)</span> we use the values of the elements <span class=\"math inline\">\\(a_0\\)</span> and <span class=\"math inline\">\\(a_1\\)</span>.</p>\n<ul>\n<li>For <span class=\"math inline\">\\(n=0\\)</span>, we know that <span class=\"math inline\">\\(a_0=\\var{a0}\\)</span>, and our general form gives us that this must be equal to <span class=\"math inline\">\\(a_0 = s_0*(\\var{x1})^0 + s_2*(\\var{x2})^0.\\)</span></li>\n<li>For <span class=\"math inline\">\\(n=1\\)</span>, we know that <span class=\"math inline\">\\(a_1=\\var{a1}\\)</span>, and our general form gives us that this must be equal to <span class=\"math inline\">\\(a_1 = s_1*(\\var{x1})^1 + s_2*(\\var{x2})^1.\\)</span></li>\n</ul>\n<p>And so we obtain the simultaneous equations: <span class=\"math display\">\\[ \\begin{cases} s_1 + s_2 &amp;= \\var{a0}\\\\ \\simplify{+{x1}*s_1 +{x2}*s_2} &amp;= \\var{a1} \\end{cases}. \\]</span></p>\n<p><span class=\"math display\">We can solve this system of linear equations, for example by elimination. Let's eliminate $s_2$:</span></p>\n<ol>\n<li>Multiply the top equation by $\\var{x2}$ (the coefficient of $s_2$ in the bottom equation): $\\simplify{{x2}*s_1 + {x2}*s_2}=\\var{x2*a0}$.</li>\n<li>Subtract the second equation from the first: \\[\\simplify{({x2}-{x1})*s_1} = \\var{x2*a0-a1}.\\]</li>\n<li>Solve for $s_1$ using the equation we just obtained: $s_1=\\var{s1}$.</li>\n<li>Substitute the value of $s_1$ into the top equation: $s_2=\\var{a0}-s_1 = \\var{s2}$.</li>\n</ol>\n<p>We find that <span class=\"math inline\">\\(s_1 = \\var{s1}\\)</span> and <span class=\"math inline\">\\(s_2=\\var{s2}\\)</span>. <strong>Make sure to verify your intermediate result at this stage by plugging these values back into the two simultaneous equations.</strong></p>\n<p>Therefore the closed form is <span class=\"math display\">\\[a_n = \\var{closedForm}.\\]</span> <strong>Evaluate at least <span class=\"math inline\">\\(a_0\\)</span>, <span class=\"math inline\">\\(a_1\\)</span> and <span class=\"math inline\">\\(a_2\\)</span> with your closed form solution before entering it into the quiz.</strong></p>", "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": "random(-5..5)", "description": "", "templateType": "anything", "can_override": false}, "s1": {"name": "s1", "group": "Randomised parameters", "definition": "random(-3..3)", "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": "roots[1]", "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}}, "variablesTest": {"condition": "not (roots[0] = -roots[1])", "maxRuns": 100}, "ungrouped_variables": ["test"], "variable_groups": [{"name": "Parameters", "variables": ["rootSet", "order"]}, {"name": "Randomised parameters", "variables": ["roots", "s1", "s2"]}, {"name": "Generated Values", "variables": ["charac", "c1", "c2", "closedForm", "a0", "a1", "recurrence"]}, {"name": "Feedback", "variables": ["a2", "a3"]}, {"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": "jme", "useCustomName": false, "customName": "", "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(\"<p>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}$.<p><p>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.</p>\"),[\"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(\"<p>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}$.</p> <p>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.</p>\"),[\"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(\"<p>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}$.</p><p>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.</p>\"),[\"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, "prompt": "<p><strong>Note the index! </strong> $a_n =$</p>", "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": []}], "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/"}]}