// Numbas version: finer_feedback_settings
{"name": "Strong Induction", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"ungrouped_variables": ["A", "B", "root1", "root2", "k"], "advice": "<p>Proof by induction always has a base case and inductive step. In part a we are asked to show</p>\n<p style=\"text-align: center;\">$f(0) =&nbsp;\\var{A}\\times\\var{root1}^0 + \\var{B}\\times\\var{root2}^0 = \\var{A + B} = u_0$,</p>\n<p style=\"text-align: center;\">$f(1) = \\var{A}\\times\\var{root1}^1 + \\var{B}\\times\\var{root2}^1 = \\var{root1*A + root2*B} = u_1.$</p>\n<p style=\"text-align: left;\">In part b we fix $n$ and assume that $f(k) = u_k$ for $2 \\leq k \\leq n$. That is, assume</p>\n<p style=\"text-align: center;\">$ u_k = &nbsp;\\var{A}\\times\\var{root1}^k + \\var{B}\\times\\var{root2}^k. $</p>\n<p style=\"text-align: left;\">In strong induction you usually assume all of the previous cases hold ($f(k)=u_k$ is true for all $2\\leq k\\leq n$). This works generally, but here we end up using only the assumptions that $u_n = f(n)$ and $u_{n-1}=f(n-1)$.</p>\n<table style=\"margin-left: auto; margin-right: auto;\">\n<tbody>\n<tr>\n<td style=\"text-align: right;\">$ u_{n+1}$</td>\n<td style=\"text-align: left;\">$&nbsp;= \\var{root1 + root2} u_{n} - \\var{root1*root2}u_{n-1} $&nbsp;</td>\n</tr>\n<tr>\n<td></td>\n<td style=\"text-align: left;\">$ = \\var{root1 + root2} (\\var{A}\\times\\var{root1}^n + \\var{B}\\times\\var{root2}^n) - \\var{root1*root2}(\\var{A}\\times\\var{root1}^{n-1} + \\var{B}\\times\\var{root2}^{n-1}) $</td>\n</tr>\n<tr>\n<td></td>\n<td style=\"text-align: left;\">$= (\\var{root1 + root2}\\times\\var{A}\\times\\var{root1} - \\var{root1*root2}\\times\\var{A})\\var{root1}^{n-1} + (\\var{root1 + root2}\\times\\var{B}\\times\\var{root2} - \\var{root1*root2}\\times\\var{B})\\var{root2}^{n-1} $</td>\n</tr>\n<tr>\n<td></td>\n<td>\n<p style=\"text-align: left;\">$ = \\simplify{({root1}+{root2})*{A}*{root1} - {root1}*{root2}*{A}}\\times\\var{root1}^{n-1} + \\simplify{({root1}+{root2})*{B}*{root2} - {root1}*{root2}*{B}}\\times\\var{root2}^{n-1} $</p>\n</td>\n</tr>\n<tr>\n<td></td>\n<td>\n<p style=\"text-align: left;\">$= \\simplify{(({root1}+{root2})*{A}*{root1} - {root1}*{root2}*{A})/{root1}^2}\\times\\var{root1}^{n+1} + \\simplify{(({root1}+{root2})*{B}*{root2} - {root1}*{root2}*{B})/{root2}^2}\\times\\var{root2}^{n+1}$</p>\n</td>\n</tr>\n</tbody>\n</table>\n<p style=\"text-align: left;\">Hence $f(n) = u_n$ for all $n = 0,1,\\cdots$ by induction.</p>", "variable_groups": [], "tags": [], "variablesTest": {"condition": "", "maxRuns": 100}, "functions": {}, "rulesets": {}, "variables": {"root1": {"definition": "random(2..9)", "group": "Ungrouped variables", "name": "root1", "templateType": "anything", "description": ""}, "root2": {"definition": "random(2..6 except root1)", "group": "Ungrouped variables", "name": "root2", "templateType": "anything", "description": ""}, "A": {"definition": "random(-5..6 except [-1,0,1])", "group": "Ungrouped variables", "name": "A", "templateType": "anything", "description": ""}, "B": {"definition": "random(2..7 except [A])", "group": "Ungrouped variables", "name": "B", "templateType": "anything", "description": ""}, "k": {"definition": "random(10..20)", "group": "Ungrouped variables", "name": "k", "templateType": "anything", "description": ""}}, "statement": "<p><strong>Strong induction</strong> is the name given to induction that makes more assumptions in the inductive step. Consider the sequence of numbers $u_0, u_1, u_2, \\cdots$ defined by</p>\n<p style=\"text-align: center;\">$\\begin{align*} u_0 &amp; = \\var{A+B} \\\\ u_1 &amp; = \\var{A*root1 + B*root2} \\\\ u_n &amp; = \\var{root1 + root2} u_{n-1} - \\var{root1*root2}u_{n-2} \\text{ for } n \\geq 2. \\end{align*}$</p>\n<p style=\"text-align: left;\">Prove by strong induction that $f(n) = \\simplify{{A}*{root1}^n + {B}*{root2}^n} = u_n$.</p>", "extensions": [], "preamble": {"js": "", "css": ""}, "name": "Strong Induction", "parts": [{"unitTests": [], "sortAnswers": false, "prompt": "<p style=\"text-align: left;\">Since the general term is defined by the two terms preceding it, the first two terms $u_0$ and $u_1$ are both base cases.</p>\n<p style=\"text-align: left;\">Prove the <strong>base cases</strong>:</p>\n<p style=\"text-align: center;\">$f(0) =&nbsp;\\var{A}\\times\\var{root1}^0 + \\var{B}\\times\\var{root2}^0 = $&nbsp;[[0]]</p>\n<p style=\"text-align: center;\">$f(1) = \\var{A}\\times\\var{root1}^1 + \\var{B}\\times\\var{root2}^1 = $ [[1]].</p>", "showFeedbackIcon": true, "showCorrectAnswer": true, "marks": 0, "customMarkingAlgorithm": "", "scripts": {}, "variableReplacements": [], "type": "gapfill", "extendBaseMarkingAlgorithm": true, "customName": "", "gaps": [{"unitTests": [], "maxValue": "{A + B}", "allowFractions": false, "showFeedbackIcon": true, "showCorrectAnswer": true, "marks": "0.5", "customMarkingAlgorithm": "", "scripts": {}, "minValue": "{A + B}", "notationStyles": ["plain", "en", "si-en"], "variableReplacements": [], "mustBeReduced": false, "type": "numberentry", "extendBaseMarkingAlgorithm": true, "customName": "", "showFractionHint": true, "useCustomName": false, "correctAnswerStyle": "plain", "correctAnswerFraction": false, "variableReplacementStrategy": "originalfirst", "mustBeReducedPC": 0}, {"unitTests": [], "maxValue": "{root1*A + root2*B}", "allowFractions": false, "showFeedbackIcon": true, "showCorrectAnswer": true, "marks": "0.5", "customMarkingAlgorithm": "", "scripts": {}, "minValue": "{root1*A + root2*B}", "notationStyles": ["plain", "en", "si-en"], "variableReplacements": [], "mustBeReduced": false, "type": "numberentry", "extendBaseMarkingAlgorithm": true, "customName": "", "showFractionHint": true, "useCustomName": false, "correctAnswerStyle": "plain", "correctAnswerFraction": false, "variableReplacementStrategy": "originalfirst", "mustBeReducedPC": 0}], "useCustomName": false, "variableReplacementStrategy": "originalfirst"}, {"unitTests": [], "sortAnswers": false, "prompt": "<p><strong>Induction step:&nbsp;</strong>Assume for each integer $2 \\leq k \\leq n$ that:</p>\n<p style=\"text-align: center;\">$u_k = $ [[0]]</p>\n<p>Using the assumptions that you just made, show that $f(n+1)=u_{n+1}$. That is:</p>\n<p style=\"text-align: center;\">$u_{n+1} =\\var{root1 + root2} u_{n} - \\var{root1*root2}u_{n-1} = $ [[1]].</p>\n<p style=\"text-align: center;\"></p>\n<p style=\"text-align: left;\"></p>", "showFeedbackIcon": true, "showCorrectAnswer": true, "marks": 0, "customMarkingAlgorithm": "", "scripts": {}, "variableReplacements": [], "type": "gapfill", "extendBaseMarkingAlgorithm": true, "customName": "", "gaps": [{"unitTests": [], "answer": "{A}*{root1}^k + {B}*{root2}^k", "failureRate": 1, "showFeedbackIcon": true, "showCorrectAnswer": true, "marks": 1, "customMarkingAlgorithm": "", "scripts": {}, "vsetRangePoints": 5, "checkVariableNames": true, "variableReplacements": [], "checkingAccuracy": 0.001, "type": "jme", "extendBaseMarkingAlgorithm": true, "valuegenerators": [{"value": "", "name": "k"}], "customName": "", "showPreview": true, "useCustomName": false, "checkingType": "absdiff", "variableReplacementStrategy": "originalfirst", "vsetRange": [0, 1]}, {"unitTests": [], "answer": "{A}*{root1}^(n+1) + {B}*{root2}^(n+1)", "failureRate": 1, "showFeedbackIcon": true, "showCorrectAnswer": true, "marks": 1, "customMarkingAlgorithm": "", "scripts": {}, "vsetRangePoints": 5, "checkVariableNames": true, "variableReplacements": [], "checkingAccuracy": 0.001, "type": "jme", "extendBaseMarkingAlgorithm": true, "valuegenerators": [{"value": "", "name": "n"}], "customName": "", "showPreview": true, "useCustomName": false, "checkingType": "absdiff", "variableReplacementStrategy": "originalfirst", "vsetRange": [0, 1]}], "useCustomName": false, "variableReplacementStrategy": "originalfirst"}, {"unitTests": [], "prompt": "<p style=\"text-align: left;\">The base case gives that $u_0=f(0)$ and $u_1=f(1)$. The first iteration of the induction step uses these assumptions to prove $u_2 = f(2)$. A second iteration uses proves that $f(3) = u_3$ and so on. Hence $f(n)=u_n$ for evey integer $n \\geq 0$.</p>", "showFeedbackIcon": true, "showCorrectAnswer": true, "marks": 0, "customMarkingAlgorithm": "", "scripts": {}, "variableReplacements": [], "type": "information", "extendBaseMarkingAlgorithm": true, "customName": "", "useCustomName": false, "variableReplacementStrategy": "originalfirst"}], "metadata": {"licence": "Creative Commons Attribution-ShareAlike 4.0 International", "description": "<p>Intorduces strong induction and uses it to verify the solutions of a second order linear recurrence.</p>"}, "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/"}]}