Explaining the proof of Fibonacci number using inductive reasoning
Fibonacci numbers are defined as follows.
$$F_{1}= F_{2} = 1$$
When $n geq 3$, $$F_{n} = F_{n-1} + F_{n-2}$$
Task: Prove the following statement using mathematical induction:
- When $n geq 2$, $$F_{n-1}F_{n+1} = F_{n}^2 + (-1)^n$$
The Base Case:
The Inductive Step:
I'm really confused about the inductive step. The answer makes absolutely no sense to me.
Questions:
- For the inductive step, why is the yellow area equal to the green area?
- For the inductive step, how do we arrive at the purple and red statement?
I think the answer given to me is too simplified and doesn't demonstrate a clear logical reasoning.
induction fibonacci-numbers
edited Dec 10 '18 at 11:44
amWhy
191k28224439
asked Dec 9 '18 at 22:15
potatoguy
525
add a comment |
Fibonacci numbers are defined as follows.
$$F_{1}= F_{2} = 1$$
When $n geq 3$, $$F_{n} = F_{n-1} + F_{n-2}$$
Task: Prove the following statement using mathematical induction:
- When $n geq 2$, $$F_{n-1}F_{n+1} = F_{n}^2 + (-1)^n$$
The Base Case:
The Inductive Step:
I'm really confused about the inductive step. The answer makes absolutely no sense to me.
Questions:
- For the inductive step, why is the yellow area equal to the green area?
- For the inductive step, how do we arrive at the purple and red statement?
I think the answer given to me is too simplified and doesn't demonstrate a clear logical reasoning.
induction fibonacci-numbers
edited Dec 10 '18 at 11:44
amWhy
191k28224439
asked Dec 9 '18 at 22:15
potatoguy
525
My apologies for anyone who is color blind. It's just easier for me to color code the statements.
– potatoguy
Dec 9 '18 at 22:18
add a comment |
Fibonacci numbers are defined as follows.
$$F_{1}= F_{2} = 1$$
When $n geq 3$, $$F_{n} = F_{n-1} + F_{n-2}$$
Task: Prove the following statement using mathematical induction:
- When $n geq 2$, $$F_{n-1}F_{n+1} = F_{n}^2 + (-1)^n$$
The Base Case:
The Inductive Step:
I'm really confused about the inductive step. The answer makes absolutely no sense to me.
Questions:
- For the inductive step, why is the yellow area equal to the green area?
- For the inductive step, how do we arrive at the purple and red statement?
I think the answer given to me is too simplified and doesn't demonstrate a clear logical reasoning.
induction fibonacci-numbers
edited Dec 10 '18 at 11:44
amWhy
191k28224439
asked Dec 9 '18 at 22:15
potatoguy
525
Fibonacci numbers are defined as follows.
$$F_{1}= F_{2} = 1$$
When $n geq 3$, $$F_{n} = F_{n-1} + F_{n-2}$$
Task: Prove the following statement using mathematical induction:
- When $n geq 2$, $$F_{n-1}F_{n+1} = F_{n}^2 + (-1)^n$$
The Base Case:
The Inductive Step:
I'm really confused about the inductive step. The answer makes absolutely no sense to me.
Questions:
- For the inductive step, why is the yellow area equal to the green area?
- For the inductive step, how do we arrive at the purple and red statement?
I think the answer given to me is too simplified and doesn't demonstrate a clear logical reasoning.
induction fibonacci-numbers
induction fibonacci-numbers
edited Dec 10 '18 at 11:44
amWhy
191k28224439
asked Dec 9 '18 at 22:15
potatoguy
525
edited Dec 10 '18 at 11:44
amWhy
191k28224439
asked Dec 9 '18 at 22:15
potatoguy
525
edited Dec 10 '18 at 11:44
amWhy
191k28224439
edited Dec 10 '18 at 11:44
amWhy
191k28224439
edited Dec 10 '18 at 11:44
amWhy
191k28224439
191k28224439
asked Dec 9 '18 at 22:15
potatoguy
525
asked Dec 9 '18 at 22:15
potatoguy
525
asked Dec 9 '18 at 22:15
potatoguy
525
525
My apologies for anyone who is color blind. It's just easier for me to color code the statements.
– potatoguy
Dec 9 '18 at 22:18
add a comment |
My apologies for anyone who is color blind. It's just easier for me to color code the statements.
– potatoguy
Dec 9 '18 at 22:18
My apologies for anyone who is color blind. It's just easier for me to color code the statements.
– potatoguy
Dec 9 '18 at 22:18
My apologies for anyone who is color blind. It's just easier for me to color code the statements.
– potatoguy
Dec 9 '18 at 22:18
add a comment |
2 Answers
2
active
oldest
votes
The green part is
$$f^2(k)+f(k)f(k+1)=(f(k-1)+f(k))f(k+1)-(-1)^k=f^2(k+1)+(-1)^{k+1},$$
i.e. the yellow part. Note that it's not supposed to be obvious at this stage that green = yellow; that they are is what the subsequent lines show. The important part is that red - yellow; that's why the inductive step works. The way the proof of this actually starts is by rewriting $f(k+2)$ as a sum to get the green expression.The purple part is equal to the line above it, by summing the coefficients of $f(k+1)$ and taking care with powers of $-1$. The red part rewrites the summed coefficient from the recursion relation, and then notes a square is present.
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
add a comment |
- Because, by definition, $f(k+2)=f(k+1)+f(k)$.
- First of all, $-(-1)^k=(-1)times(-1)^k=(-1)^{k+1}$. Then,$$f(k)f(k+1)+f(k-1)f(k+1)=bigl(f(k)+f(k-1)bigr)f(k+1).$$So,$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k)+f(k-1)bigr)f(k+1)+(-1)^{k+1}.tag1$$But, by definition, $f(k+1)=f(k)+f(k-1)$. So, $(1)$ becomes$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k+1)bigr)^2+(-1)^{k+1}.$$
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
1. asked about the green expression, not the blue one.
– J.G.
Dec 9 '18 at 22:25
I've edited my answer. I hope that everything is clear now.
– José Carlos Santos
Dec 9 '18 at 22:29
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033105%2fexplaining-the-proof-of-fibonacci-number-using-inductive-reasoning%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
The green part is
$$f^2(k)+f(k)f(k+1)=(f(k-1)+f(k))f(k+1)-(-1)^k=f^2(k+1)+(-1)^{k+1},$$
i.e. the yellow part. Note that it's not supposed to be obvious at this stage that green = yellow; that they are is what the subsequent lines show. The important part is that red - yellow; that's why the inductive step works. The way the proof of this actually starts is by rewriting $f(k+2)$ as a sum to get the green expression.The purple part is equal to the line above it, by summing the coefficients of $f(k+1)$ and taking care with powers of $-1$. The red part rewrites the summed coefficient from the recursion relation, and then notes a square is present.
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
add a comment |
The green part is
$$f^2(k)+f(k)f(k+1)=(f(k-1)+f(k))f(k+1)-(-1)^k=f^2(k+1)+(-1)^{k+1},$$
i.e. the yellow part. Note that it's not supposed to be obvious at this stage that green = yellow; that they are is what the subsequent lines show. The important part is that red - yellow; that's why the inductive step works. The way the proof of this actually starts is by rewriting $f(k+2)$ as a sum to get the green expression.The purple part is equal to the line above it, by summing the coefficients of $f(k+1)$ and taking care with powers of $-1$. The red part rewrites the summed coefficient from the recursion relation, and then notes a square is present.
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
add a comment |
The green part is
$$f^2(k)+f(k)f(k+1)=(f(k-1)+f(k))f(k+1)-(-1)^k=f^2(k+1)+(-1)^{k+1},$$
i.e. the yellow part. Note that it's not supposed to be obvious at this stage that green = yellow; that they are is what the subsequent lines show. The important part is that red - yellow; that's why the inductive step works. The way the proof of this actually starts is by rewriting $f(k+2)$ as a sum to get the green expression.The purple part is equal to the line above it, by summing the coefficients of $f(k+1)$ and taking care with powers of $-1$. The red part rewrites the summed coefficient from the recursion relation, and then notes a square is present.
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
The green part is
$$f^2(k)+f(k)f(k+1)=(f(k-1)+f(k))f(k+1)-(-1)^k=f^2(k+1)+(-1)^{k+1},$$
i.e. the yellow part. Note that it's not supposed to be obvious at this stage that green = yellow; that they are is what the subsequent lines show. The important part is that red - yellow; that's why the inductive step works. The way the proof of this actually starts is by rewriting $f(k+2)$ as a sum to get the green expression.The purple part is equal to the line above it, by summing the coefficients of $f(k+1)$ and taking care with powers of $-1$. The red part rewrites the summed coefficient from the recursion relation, and then notes a square is present.
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
answered Dec 9 '18 at 22:25
J.G.
22.6k22136
22.6k22136
add a comment |
add a comment |
- Because, by definition, $f(k+2)=f(k+1)+f(k)$.
- First of all, $-(-1)^k=(-1)times(-1)^k=(-1)^{k+1}$. Then,$$f(k)f(k+1)+f(k-1)f(k+1)=bigl(f(k)+f(k-1)bigr)f(k+1).$$So,$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k)+f(k-1)bigr)f(k+1)+(-1)^{k+1}.tag1$$But, by definition, $f(k+1)=f(k)+f(k-1)$. So, $(1)$ becomes$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k+1)bigr)^2+(-1)^{k+1}.$$
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
1. asked about the green expression, not the blue one.
– J.G.
Dec 9 '18 at 22:25
I've edited my answer. I hope that everything is clear now.
– José Carlos Santos
Dec 9 '18 at 22:29
add a comment |
- Because, by definition, $f(k+2)=f(k+1)+f(k)$.
- First of all, $-(-1)^k=(-1)times(-1)^k=(-1)^{k+1}$. Then,$$f(k)f(k+1)+f(k-1)f(k+1)=bigl(f(k)+f(k-1)bigr)f(k+1).$$So,$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k)+f(k-1)bigr)f(k+1)+(-1)^{k+1}.tag1$$But, by definition, $f(k+1)=f(k)+f(k-1)$. So, $(1)$ becomes$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k+1)bigr)^2+(-1)^{k+1}.$$
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
1. asked about the green expression, not the blue one.
– J.G.
Dec 9 '18 at 22:25
I've edited my answer. I hope that everything is clear now.
– José Carlos Santos
Dec 9 '18 at 22:29
add a comment |
- Because, by definition, $f(k+2)=f(k+1)+f(k)$.
- First of all, $-(-1)^k=(-1)times(-1)^k=(-1)^{k+1}$. Then,$$f(k)f(k+1)+f(k-1)f(k+1)=bigl(f(k)+f(k-1)bigr)f(k+1).$$So,$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k)+f(k-1)bigr)f(k+1)+(-1)^{k+1}.tag1$$But, by definition, $f(k+1)=f(k)+f(k-1)$. So, $(1)$ becomes$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k+1)bigr)^2+(-1)^{k+1}.$$
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
- Because, by definition, $f(k+2)=f(k+1)+f(k)$.
- First of all, $-(-1)^k=(-1)times(-1)^k=(-1)^{k+1}$. Then,$$f(k)f(k+1)+f(k-1)f(k+1)=bigl(f(k)+f(k-1)bigr)f(k+1).$$So,$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k)+f(k-1)bigr)f(k+1)+(-1)^{k+1}.tag1$$But, by definition, $f(k+1)=f(k)+f(k-1)$. So, $(1)$ becomes$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=bigl(f(k+1)bigr)^2+(-1)^{k+1}.$$
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
edited Dec 9 '18 at 22:29
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
answered Dec 9 '18 at 22:23
José Carlos Santos
150k22121221
150k22121221
1. asked about the green expression, not the blue one.
– J.G.
Dec 9 '18 at 22:25
I've edited my answer. I hope that everything is clear now.
– José Carlos Santos
Dec 9 '18 at 22:29
add a comment |
1. asked about the green expression, not the blue one.
– J.G.
Dec 9 '18 at 22:25
I've edited my answer. I hope that everything is clear now.
– José Carlos Santos
Dec 9 '18 at 22:29
1. asked about the green expression, not the blue one.
– J.G.
Dec 9 '18 at 22:25
1. asked about the green expression, not the blue one.
– J.G.
Dec 9 '18 at 22:25
I've edited my answer. I hope that everything is clear now.
– José Carlos Santos
Dec 9 '18 at 22:29
I've edited my answer. I hope that everything is clear now.
– José Carlos Santos
Dec 9 '18 at 22:29
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033105%2fexplaining-the-proof-of-fibonacci-number-using-inductive-reasoning%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
My apologies for anyone who is color blind. It's just easier for me to color code the statements.
– potatoguy
Dec 9 '18 at 22:18