// Numbas version: exam_results_page_options
{"name": "Order 1 Recurrence", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Order 1 Recurrence", "tags": [], "metadata": {"description": "<p>In this question the students have to solve a linear recurrence of order 1. 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>Find the closed form of the relations:</p>\n<p>\\begin{cases} a_0 &amp;= \\var{a0}\\\\ a_n &amp;= \\simplify{{recurrence}} \\end{cases}</p>", "advice": "<p>To solve Order 1 recurrences, we need to apply the following steps:</p>\n<ol type=\"1\">\n<li>Express the recurrence relation for the first difference (which <em>will</em> be a geometric sequence).</li>\n<li>Find the closed form for that geometric sequence.</li>\n<li>Find the closed form of the original sequence using its first difference.</li>\n</ol>\n<h2 id=\"finding-the-first-difference.\">Finding the first difference.</h2>\n<p>We need two things here: the first element, and the recurrence formula for the first difference.</p>\n<p>For the first element, we have <span class=\"math inline\">\\(b_0 = a_1-a_0\\)</span>.</p>\n<ul>\n<li><span class=\"math inline\">\\(a_0 = \\var{a0}\\)</span></li>\n<li><span class=\"math inline\">\\(a_1 = \\var{a1rec} = \\var{a1}\\)</span>.</li>\n</ul>\n<p>So, <span class=\"math inline\">\\(b_0 = \\var{a1} - \\var{a0} = \\var{b0}\\)</span>.</p>\n<p>For the recurrence formula, we have</p>\n<p><span class=\"math display\">\\[\\begin{aligned} b_n &amp;= a_{n+1} - a_{n}\\\\ &amp;= \\var{bndiff}\\\\ &amp;= \\var{bnrec} \\end{aligned}\\]</span></p>\n<h2 id=\"closed-form-of-the-first-difference.\">Closed form of the first difference.</h2>\n<p>Now we know that the first difference is a geometric sequence, and we know its recurrence form. From Activity 2, we can find the closed form: <span class=\"math inline\">\\(b_0\\times k^n\\)</span>, where <span class=\"math inline\">\\(k\\)</span> is the multiplier in the recurrence. So <span class=\"math display\">\\[ b_0 = \\var{bnclosed} \\]</span></p>\n<h2 id=\"closed-form-for-the-sequence-a_n\">Closed form for the sequence <span class=\"math inline\">\\(a_n\\)</span>:</h2>\n<p>Finally we can use the closed form of the first difference to find <span class=\"math inline\">\\(a_n\\)</span>.</p>\n<p><span class=\"math display\">\\[\\begin{aligned} b_n &amp;= a_{n+1} - a_{n}\\\\ \\var{bnclosed} &amp;= \\var{an1rec} - a_{n}\\\\ &amp;= \\var{bnstep1}\\\\ \\var{bnstep2lhs} &amp;= \\var{bnstep2rhs}\\\\ \\var{closedForm} &amp;= a_n &amp;\\text{divide both sides by }\\simplify{{k}-1} \\end{aligned}\\]</span></p>\n<p>And so we find the closed form for <span class=\"math inline\">\\(a_n\\)</span>.</p>", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"k": {"name": "k", "group": "Question Parameters", "definition": "random(-10..10 except 0 except 1)", "description": "", "templateType": "anything", "can_override": false}, "r": {"name": "r", "group": "Question Parameters", "definition": "random(-3..3 except 0 except -1)", "description": "", "templateType": "anything", "can_override": false}, "a0": {"name": "a0", "group": "Question", "definition": "k+d", "description": "", "templateType": "anything", "can_override": false}, "recurrence": {"name": "recurrence", "group": "Question", "definition": "expression(\"{k}*sub(a,n-1)+{d}\")", "description": "", "templateType": "anything", "can_override": false}, "closedForm": {"name": "closedForm", "group": "solution", "definition": "simplify(expression(\"{v}*({k})^n-{r}\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "v": {"name": "v", "group": "solution", "definition": "a0+r", "description": "", "templateType": "anything", "can_override": false}, "d": {"name": "d", "group": "Question", "definition": "r*(k-1)", "description": "", "templateType": "anything", "can_override": false}, "a1": {"name": "a1", "group": "Advice - part 1", "definition": "k*a0+d", "description": "", "templateType": "anything", "can_override": false}, "a1rec": {"name": "a1rec", "group": "Advice - part 1", "definition": "expression(\"{k}* sub(a,0) +{d}\")", "description": "", "templateType": "anything", "can_override": false}, "b0": {"name": "b0", "group": "Advice - part 1", "definition": "a1-a0", "description": "", "templateType": "anything", "can_override": false}, "an1rec": {"name": "an1rec", "group": "Advice - part 1", "definition": "simplify(expression(\"{k}*sub(a,n)+{d}\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "bnrec": {"name": "bnrec", "group": "Advice - part 1", "definition": "simplify(expression(\"{k}*sub(b,n-1)\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "anrec": {"name": "anrec", "group": "Advice - part 1", "definition": "simplify(expression(\"{k}*sub(a,n-1)+{d}\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "bndiff": {"name": "bndiff", "group": "Advice - part 1", "definition": "simplify(expression(\"({an1rec})-({anrec})\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "bnclosed": {"name": "bnclosed", "group": "Advice - part 2", "definition": "expression(\"{b0}*({k})^n\")", "description": "", "templateType": "anything", "can_override": false}, "bnstep1": {"name": "bnstep1", "group": "Adviced - part 3", "definition": "simplify(expression(\"{an1rec}-sub(a,n)\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "bnstep2lhs": {"name": "bnstep2lhs", "group": "Adviced - part 3", "definition": "simplify(expression(\"{bnclosed}-{d}\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "bnstep2rhs": {"name": "bnstep2rhs", "group": "Adviced - part 3", "definition": "simplify(expression(\"{k-1}*sub(a,n)\"),[\"basic\"])", "description": "", "templateType": "anything", "can_override": false}, "a2": {"name": "a2", "group": "Ungrouped variables", "definition": "k*a1+d", "description": "", "templateType": "anything", "can_override": false}, "a22": {"name": "a22", "group": "Ungrouped variables", "definition": "eval(closedForm,['n':2])", "description": "", "templateType": "anything", "can_override": false}, "test": {"name": "test", "group": "Ungrouped variables", "definition": "substitute([n:0],closedform)", "description": "", "templateType": "anything", "can_override": false}, "test2": {"name": "test2", "group": "Ungrouped variables", "definition": "subvalue(closedform,3)", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["a2", "a22", "test", "test2"], "variable_groups": [{"name": "Question Parameters", "variables": ["k", "r"]}, {"name": "solution", "variables": ["v", "closedForm"]}, {"name": "Question", "variables": ["a0", "d", "recurrence"]}, {"name": "Advice - part 1", "variables": ["a1rec", "a1", "b0", "an1rec", "bnrec", "anrec", "bndiff"]}, {"name": "Advice - part 2", "variables": ["bnclosed"]}, {"name": "Adviced - part 3", "variables": ["bnstep1", "bnstep2lhs", "bnstep2rhs"]}], "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(\"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}$\"),[\"nex\":subvalue(studentCompare,0),\"nv\":eval(studentCompare,['n':0])])))\n    \naone (check that the student's answer is correct for n=1):\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}$\"),[\"nex\":subvalue(studentCompare,1),\"nv\":eval(studentCompare,['n':1])])))\n\nmark:\n    apply(studentExpr);\n    apply(failNameToCompare);\n    apply(unexpectedVariables);\n    apply(sameVars);\n    apply(azero);\n    apply(aone);\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", "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/"}]}