// Numbas version: finer_feedback_settings
{"name": "Induktion (Fibonacci-Zahlen)", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Induktion (Fibonacci-Zahlen)", "tags": [], "metadata": {"description": "<p>An induction problem concerning the Fibonacci sequence.</p>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>Wir definieren die Folge der Fibonacci-Zahlen durch</p>\n<p>\\[ F_0 = 0,\\quad F_1 = 1,\\quad F_n = F_{n-1}+F_{n-2}\\ \\text{f&uuml;r}\\ n\\ge 2.\\]</p>\n<p>Siehe <a href=\"https://math.ug/la1-ws2021/subsec-anwendungen.html#frage-fibonacci\" target=\"_blank\" rel=\"noopener noreferrer\" title=\"Fibonacci-Folge im Vorlesungsskript\">Frage 2.1</a> im Skript f&uuml;r weitere Verweise.</p>", "advice": "<p><strong>a)</strong></p>\n<p>Da hier keine sehr hohen Indizes auftreten, kann man einfach die ersten Terme der Fibonacci-Folge anhand der rekursiven Definition ausrechnen:</p>\n<p>\\[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \\dots \\]</p>\n<p><strong>b)</strong></p>\n<p>In der Summe werden die Fibonacci-Zahlen bis $F_{\\var{nn}}$ aufsummiert, aber mit wechselndem (\"alternierendem\") Vorzeichen, denn $(-1)^1 = -1$, $(-1)^2 = 1$, $(-1)^3 = -1$, usw.</p>\n<p>Es ist also</p>\n<p>\\[ \\sum_{i=1}^{\\var{nn}} (-1)^{i+1} F_i = (-1)^2 F_1 + (-1)^3 F_2 + (-1)^4 F_3 + \\cdots + (-1)^{\\var{nn+1}} F_{\\var{nn}}&nbsp; = F_1 - F_2 + F_3 - \\cdots \\var{sgnnpo} F_{\\var{nn}}. \\]</p>\n<p></p>\n<p><strong>c)</strong></p>\n<p>Hier noch einmal der vollst&auml;ndige Beweis:</p>\n<p>Behauptung: F&uuml;r alle nat&uuml;rlichen Zahlen $n\\ge 1$ gilt: \\[ \\sum_{i=1}^n (-1)^{i+1} F_i = (-1)^{n-1}F_{n-1} + 1.\\]</p>\n<p></p>\n<p>Beweis durch vollst&auml;ndige Induktion nach $n$.</p>\n<p>Induktionsanfang $n=1$. Die linke Seite ist $\\sum_{i=1}^1 (-1)^{i+1} F_i = F_1 = 1$, die rechte Seite ist $(-1)^{1-1}F_{1-1} + 1 = F_0+1=1$. Der Induktionsanfang ist also richtig.</p>\n<p>Induktionsschritt $n&gt;1$. Wir wollen zeigen, dass $\\sum_{i=1}^n (-1)^{i+1} F_i = (-1)^{n-1}F_{n-1} + 1$. Dabei d&uuml;rfen wir die Induktionsvoraussetzung benutzen:</p>\n<p>\\[ \\sum_{i=1}^{n-1} (-1)^{i+1} F_i = (-1)^{n-2}F_{n-2} + 1. \\]</p>\n<p>Wir schreiben</p>\n<p>\\begin{align} \\sum_{i=1}^n (-1)^{i+1} F_i &amp; = \\sum_{i=1}^{n-1} (-1)^{i+1} F_i + (-1)^{n+1} F_n \\\\ &amp; = (-1)^{n-2}F_{n-2} + 1 + (-1)^{n+1} F_n = (-1)^{n} F_{n-2} - (-1)^{n} F_n + 1, \\end{align}</p>\n<p>wobei wir im zweiten Schritt die Induktionsvoraussetzung verwendet haben, und im dritten Schritt benutzen, dass $(-1)^{n+1} = -(-1)^{n}$ und dass $(-1)^{n-2} = (-1)^{n}$ ist, denn ein Produkt von $-1$'en ist $1$ oder $-1$, je nachdem, ob die Anzahl der Faktoren gerade oder ungerade ist.</p>\n<p>Nun setzen wir die Definition von $F_n$ ein, $F_n = F_{n-1}+ F_{n-2}$, und klammern $(-1)^{n}$ aus:</p>\n<p>\\begin{align} \\sum_{i=1}^n (-1)^{i+1} F_i &amp;= (-1)^{n} (F_{n-2} - F_{n-1} - F_{n-2}) +1 = -(-1)^{n}F_{n-1} + 1 \\\\ &amp;= (-1)^{n-1} F_{n-1} + 1. \\end{align} </p>\n<p>Damit ist der Induktionsschritt abgeschlossen und die Behauptung bewiesen.</p>", "rulesets": {}, "extensions": [], "variables": {"fib1": {"name": "fib1", "group": "Ungrouped variables", "definition": "fibonacci(a1)", "description": "", "templateType": "anything"}, "fib2": {"name": "fib2", "group": "Ungrouped variables", "definition": "fibonacci(a2)", "description": "", "templateType": "anything"}, "a1": {"name": "a1", "group": "Ungrouped variables", "definition": "random(2..6)", "description": "", "templateType": "anything"}, "a2": {"name": "a2", "group": "Ungrouped variables", "definition": "random(6..10 except a1)", "description": "", "templateType": "anything"}, "nn": {"name": "nn", "group": "Ungrouped variables", "definition": "random(5..7)", "description": "", "templateType": "anything"}, "sgnnpo": {"name": "sgnnpo", "group": "Ungrouped variables", "definition": "if(mod(nn, 2), '+', '-')", "description": "<p>Sign of nn+1.</p>", "templateType": "anything"}, "": {"name": "", "group": "Ungrouped variables", "definition": "", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["fib1", "fib2", "a1", "a2", "nn", "sgnnpo", ""], "variable_groups": [], "functions": {"fibonacci": {"parameters": [["n", "number"]], "type": "anything", "language": "javascript", "definition": "if (n<=1) return n;\nvar f0 = 0;\nvar f1 = 1;\nfor(var i=0; i<n-1; i++) {\n  var f = f0;\n  f0 = f1;\n  f1 += f;\n}\n\nreturn f1"}, "F": {"parameters": [["n", "number"]], "type": "anything", "language": "jme", "definition": "fibonacci(n)"}}, "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": "<p>Geben Sie die $\\var{a1}$-te und die $\\var{a2}$-te Fibonacci-Zahl an.</p>\n<p>$F_{\\var{a1}} = $ [[0]],</p>\n<p>$F_{\\var{a2}} = $ [[1]].</p>", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{fib1}", "maxValue": "{fib1}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{fib2}", "maxValue": "{fib2}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "sortAnswers": false}, {"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": "<p>Berechnen Sie den folgenden Ausdruck:</p>\n<p>$\\sum_{i=1}^{\\var{nn}} (-1)^{i+1} F_i = $ [[0]]</p>", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{(-1)^(nn-1)*fibonacci(nn-1)+1}", "maxValue": "{(-1)^(nn-1)*fibonacci(nn-1)+1}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "sortAnswers": false}, {"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": "<p>F&uuml;llen Sie die L&uuml;cken im folgenden Text aus. Weil man komplizierte Indizes nicht direkt eingeben kann, geben Sie $F_n$ bitte in der Form $F(n)$ ein, entsprechend $(-1)^{n+1} F_{n+1}$ als <code>(-1)^(n+1) F(n+1)</code>, usw.</p>\n<p>Behauptung: F&uuml;r alle nat&uuml;rlichen Zahlen $n\\ge 1$ gilt: \\[ \\sum_{i=1}^n (-1)^{i+1} F_i = (-1)^{n-1}F_{n-1} + 1.\\]</p>\n<p>Beweis durch vollst&auml;ndige Induktion nach $n$.</p>\n<p>Induktionsanfang [[0]]. Die linke Seite ist $\\sum_{i=1}^1 (-1)^{i+1} F_i = F_1 =$ [[1]], die rechte Seite ist $(-1)^{1-1}F_{1-1} + 1 = F_0+1=$ [[2]]. Der Induktionsanfang ist also richtig.</p>\n<p>Induktionsschritt $n&gt;1$. Wir wollen zeigen, dass $\\sum_{i=1}^n (-1)^{i+1} F_i = $ [[3]]. Dabei d&uuml;rfen wir die Induktionsvoraussetzung benutzen:</p>\n<p>$\\displaystyle{ \\sum_{i=1}^{n-1} (-1)^{i+1} F_i = }$ [[4]].</p>\n<p>Wir schreiben</p>\n<p>$\\displaystyle{\\sum_{i=1}^n (-1)^{i+1} F_i&nbsp; = \\sum_{i=1}^{n-1} (-1)^{i+1} F_i + }$ [[5]]&nbsp;</p>\n<p>$\\displaystyle{ = (-1)^{n-2}F_{n-2} + 1 + (-1)^{n+1} F_n = (-1)^{n} F_{n-2} -}$ [[6]]&nbsp; $\\displaystyle{+ 1,}$</p>\n<p></p>\n<p>wobei wir im zweiten Schritt die Induktionsvoraussetzung verwendet haben, und im dritten Schritt benutzen, dass $(-1)^{n+1} = -(-1)^n$ und dass $(-1)^{n-2} = (-1)^n$ ist, denn ein Produkt von $-1$'en ist $1$ oder $-1$, je nachdem, ob die Anzahl der Faktoren gerade oder ungerade ist.</p>\n<p>Nun setzen wir die Definition von $F_n$ ein, $F_n = $ [[7]], und klammern $(-1)^n$ aus:</p>\n<p>\\begin{align} \\sum_{i=1}^n (-1)^{i+1} F_i &amp;= (-1)^n (F_{n-2} - F_{n-1} - F_{n-2}) +1 = -(-1)^nF_{n-1} + 1 \\\\ &amp;= (-1)^{n-1} F_{n-1} + 1. \\end{align}</p>\n<p>Damit ist der Induktionsschritt abgeschlossen und die Behauptung bewiesen.</p>", "gaps": [{"type": "patternmatch", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": " *n *= *1 *", "displayAnswer": "n=1", "matchMode": "regex"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "1", "maxValue": "1", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "1", "maxValue": "1", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "(-1)^(n-1)*F(n-1)+1", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": ["5", "15"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "(-1)^(n-2) F(n-2)+1", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": ["5", "15"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "(-1)^(n+1)F(n)", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": ["5", "15"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "(-1)^n F(n)", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": ["5", "15"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "F(n-1)+F(n-2)", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": ["5", "15"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": "random(5..15)"}]}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "contributors": [{"name": "Ulrich G\u00f6rtz", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7603/"}]}]}], "contributors": [{"name": "Ulrich G\u00f6rtz", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7603/"}]}