Mixing
Andrew wants to cross a 12-foot long bridge. He can either take a 1 foot step or a 2 foot step.Provide a...
$begingroup$
Other notes about the problem: Keep in mind that a 2 foot step then a 1 foot step is different than a 1 foot step then a 2 foot step.
I have found it easy to think of the bridge as a 1x12 game board using 1x1 blocks and 1x2 blocks. With that, I started with a 1x1 board and found there to be one possibility to fill the board, a 1x1 block. For a 1x2 board there are two possibilities: two 1x1 blocks or one 1x2 block. For a 1x3 board there are 3 possibilities, a 1x4 there are 5 possibilities, for a 1x5 there are 8 possibilities, and so forth. I noticed that this looked like the Fibonacci Sequence, therefore the recursive formula would look like Fn=Fn-1+Fn-2 if F1=1 and F2=2. Then we can find that there will be 233 ways for Andrew to cross the bridge.
Although I understand that the reason behind the recursive formula slightly, our professor wants a proof for how we came to the conclusion and i was unsure how to go about it. Here is what I understand thus far:
Given the 1x1 board and the 1x2 board, we can see that a 1x3 board is like the 1x2 board but with an extra 1x1 block added to the end. The 1x4 board has similar patterns to the 1x3 board, but adds an extra 1x1 block to the end and it is similar to the 1x2 board but adds two 1x1 block and one 1x2 block to the ends.
How does that work into a proof?
combinatorics proof-writing recursion fibonacci-numbers
asked Jan 28 at 23:15
LindseyLindsey
163
$endgroup$
add a comment |
$begingroup$
Other notes about the problem: Keep in mind that a 2 foot step then a 1 foot step is different than a 1 foot step then a 2 foot step.
I have found it easy to think of the bridge as a 1x12 game board using 1x1 blocks and 1x2 blocks. With that, I started with a 1x1 board and found there to be one possibility to fill the board, a 1x1 block. For a 1x2 board there are two possibilities: two 1x1 blocks or one 1x2 block. For a 1x3 board there are 3 possibilities, a 1x4 there are 5 possibilities, for a 1x5 there are 8 possibilities, and so forth. I noticed that this looked like the Fibonacci Sequence, therefore the recursive formula would look like Fn=Fn-1+Fn-2 if F1=1 and F2=2. Then we can find that there will be 233 ways for Andrew to cross the bridge.
Although I understand that the reason behind the recursive formula slightly, our professor wants a proof for how we came to the conclusion and i was unsure how to go about it. Here is what I understand thus far:
Given the 1x1 board and the 1x2 board, we can see that a 1x3 board is like the 1x2 board but with an extra 1x1 block added to the end. The 1x4 board has similar patterns to the 1x3 board, but adds an extra 1x1 block to the end and it is similar to the 1x2 board but adds two 1x1 block and one 1x2 block to the ends.
How does that work into a proof?
combinatorics proof-writing recursion fibonacci-numbers
asked Jan 28 at 23:15
LindseyLindsey
163
$endgroup$
add a comment |
$begingroup$
Other notes about the problem: Keep in mind that a 2 foot step then a 1 foot step is different than a 1 foot step then a 2 foot step.
I have found it easy to think of the bridge as a 1x12 game board using 1x1 blocks and 1x2 blocks. With that, I started with a 1x1 board and found there to be one possibility to fill the board, a 1x1 block. For a 1x2 board there are two possibilities: two 1x1 blocks or one 1x2 block. For a 1x3 board there are 3 possibilities, a 1x4 there are 5 possibilities, for a 1x5 there are 8 possibilities, and so forth. I noticed that this looked like the Fibonacci Sequence, therefore the recursive formula would look like Fn=Fn-1+Fn-2 if F1=1 and F2=2. Then we can find that there will be 233 ways for Andrew to cross the bridge.
Although I understand that the reason behind the recursive formula slightly, our professor wants a proof for how we came to the conclusion and i was unsure how to go about it. Here is what I understand thus far:
Given the 1x1 board and the 1x2 board, we can see that a 1x3 board is like the 1x2 board but with an extra 1x1 block added to the end. The 1x4 board has similar patterns to the 1x3 board, but adds an extra 1x1 block to the end and it is similar to the 1x2 board but adds two 1x1 block and one 1x2 block to the ends.
How does that work into a proof?
combinatorics proof-writing recursion fibonacci-numbers
asked Jan 28 at 23:15
LindseyLindsey
163
$endgroup$
Other notes about the problem: Keep in mind that a 2 foot step then a 1 foot step is different than a 1 foot step then a 2 foot step.
I have found it easy to think of the bridge as a 1x12 game board using 1x1 blocks and 1x2 blocks. With that, I started with a 1x1 board and found there to be one possibility to fill the board, a 1x1 block. For a 1x2 board there are two possibilities: two 1x1 blocks or one 1x2 block. For a 1x3 board there are 3 possibilities, a 1x4 there are 5 possibilities, for a 1x5 there are 8 possibilities, and so forth. I noticed that this looked like the Fibonacci Sequence, therefore the recursive formula would look like Fn=Fn-1+Fn-2 if F1=1 and F2=2. Then we can find that there will be 233 ways for Andrew to cross the bridge.
Although I understand that the reason behind the recursive formula slightly, our professor wants a proof for how we came to the conclusion and i was unsure how to go about it. Here is what I understand thus far:
Given the 1x1 board and the 1x2 board, we can see that a 1x3 board is like the 1x2 board but with an extra 1x1 block added to the end. The 1x4 board has similar patterns to the 1x3 board, but adds an extra 1x1 block to the end and it is similar to the 1x2 board but adds two 1x1 block and one 1x2 block to the ends.
How does that work into a proof?
combinatorics proof-writing recursion fibonacci-numbers
combinatorics proof-writing recursion fibonacci-numbers
asked Jan 28 at 23:15
LindseyLindsey
163
asked Jan 28 at 23:15
LindseyLindsey
163
asked Jan 28 at 23:15
LindseyLindsey
163
asked Jan 28 at 23:15
LindseyLindsey
163
asked Jan 28 at 23:15
LindseyLindsey
163
163
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You are right that this amounts to a Fibonacci sequence, and to see why, notice this:
Let's say that the number of ways to $P_n$
Now, all possible ways to cross a $n$-foot bridge can be split into two groups: one where the first step is a step of length $1$ foot, and one where the first step is a step of length $2$ feet. In the first case, there are $n-1$ feet left to cross, which by definition can be done in $P_{n-1}$ ways, and in the second case there are $n-2$ feet left to cross, which by definition can be done in $P_{n-2}$ ways
So, we have that:
$$P_n = P_{n-1}+P_{n-2}$$
and there is obviously your connection with the Fibonacci problem!
Now you just have to figure out what $P_1$ and and $P_2$ are, but that's trivial: $P_1=1$, and $P_2=2$
So, if we follow the convention that for the Fibonacci numbers we have that $F_1=F_2=1$, then we see that $P_1=F_2$, $P_2=F_3$, and thus in general that $P_n$=$F_{n+1}$
So, crossing this 12-foot bridge can be done in $P_{12}=F_{13}=233$ ways
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
$endgroup$
add a comment |
$begingroup$
You are correct that the result will be the Fibonacci sequence (with possible shifting depending on whether you start counting from zero or from one).
How I would explain it is that given a bridge of length $ngeq 2$ that he wants to traverse, he must either begin by taking a 1-foot step followed by some sequence of steps to traverse the remaining $n-1$ feet, or he begins by taking a 2-foot step followed by some sequence of steps to traverse the remaining $n-2$ feet. It is clear that these two cases cover all possibilities and do so with no overlap.
Letting $f(n)$ be the function counting the number of ways to traverse a bridge of length $n$, the above observation leads us to the familiar $f(n)=f(n-1)+f(n-2)$, here $f(n-1)$ counts the number of ways where you begin with a 1-foot step followed by a sequence of steps to traverse the remaining $n-1$ feet, and $f(n-2)$ counting the number of ways where you begin with a 2-foot step and traverse the remaining $n-2$ feet.
All that remains is to have some initial values. In this case, we need two consecutive values in order to give enough information to find all others. $f(1)=1$ should be clear. From here, you could either note that $f(2)=2$, or you could prefer to recognize that $f(0)=1$ as the empty sequence of steps still counts as a sequence of steps. Often-times by noting the existence of an empty-sequence or empty-string as a valid configuration implying that $f(0)=1$ (which is a relatively common occurrence for problems like these) this will help make finding a closed form much easier due to the nice properties of the numbers $0$ and $1$.
You see then that as the recurrence is the same as that of the Fibonacci sequence and the initial values are also the same, that this is indeed the Fibonacci sequence after all.
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
$endgroup$
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%2f3091532%2fandrew-wants-to-cross-a-12-foot-long-bridge-he-can-either-take-a-1-foot-step-or%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
$begingroup$
You are right that this amounts to a Fibonacci sequence, and to see why, notice this:
Let's say that the number of ways to $P_n$
Now, all possible ways to cross a $n$-foot bridge can be split into two groups: one where the first step is a step of length $1$ foot, and one where the first step is a step of length $2$ feet. In the first case, there are $n-1$ feet left to cross, which by definition can be done in $P_{n-1}$ ways, and in the second case there are $n-2$ feet left to cross, which by definition can be done in $P_{n-2}$ ways
So, we have that:
$$P_n = P_{n-1}+P_{n-2}$$
and there is obviously your connection with the Fibonacci problem!
Now you just have to figure out what $P_1$ and and $P_2$ are, but that's trivial: $P_1=1$, and $P_2=2$
So, if we follow the convention that for the Fibonacci numbers we have that $F_1=F_2=1$, then we see that $P_1=F_2$, $P_2=F_3$, and thus in general that $P_n$=$F_{n+1}$
So, crossing this 12-foot bridge can be done in $P_{12}=F_{13}=233$ ways
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
$endgroup$
add a comment |
$begingroup$
You are right that this amounts to a Fibonacci sequence, and to see why, notice this:
Let's say that the number of ways to $P_n$
Now, all possible ways to cross a $n$-foot bridge can be split into two groups: one where the first step is a step of length $1$ foot, and one where the first step is a step of length $2$ feet. In the first case, there are $n-1$ feet left to cross, which by definition can be done in $P_{n-1}$ ways, and in the second case there are $n-2$ feet left to cross, which by definition can be done in $P_{n-2}$ ways
So, we have that:
$$P_n = P_{n-1}+P_{n-2}$$
and there is obviously your connection with the Fibonacci problem!
Now you just have to figure out what $P_1$ and and $P_2$ are, but that's trivial: $P_1=1$, and $P_2=2$
So, if we follow the convention that for the Fibonacci numbers we have that $F_1=F_2=1$, then we see that $P_1=F_2$, $P_2=F_3$, and thus in general that $P_n$=$F_{n+1}$
So, crossing this 12-foot bridge can be done in $P_{12}=F_{13}=233$ ways
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
$endgroup$
add a comment |
$begingroup$
You are right that this amounts to a Fibonacci sequence, and to see why, notice this:
Let's say that the number of ways to $P_n$
Now, all possible ways to cross a $n$-foot bridge can be split into two groups: one where the first step is a step of length $1$ foot, and one where the first step is a step of length $2$ feet. In the first case, there are $n-1$ feet left to cross, which by definition can be done in $P_{n-1}$ ways, and in the second case there are $n-2$ feet left to cross, which by definition can be done in $P_{n-2}$ ways
So, we have that:
$$P_n = P_{n-1}+P_{n-2}$$
and there is obviously your connection with the Fibonacci problem!
Now you just have to figure out what $P_1$ and and $P_2$ are, but that's trivial: $P_1=1$, and $P_2=2$
So, if we follow the convention that for the Fibonacci numbers we have that $F_1=F_2=1$, then we see that $P_1=F_2$, $P_2=F_3$, and thus in general that $P_n$=$F_{n+1}$
So, crossing this 12-foot bridge can be done in $P_{12}=F_{13}=233$ ways
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
$endgroup$
You are right that this amounts to a Fibonacci sequence, and to see why, notice this:
Let's say that the number of ways to $P_n$
Now, all possible ways to cross a $n$-foot bridge can be split into two groups: one where the first step is a step of length $1$ foot, and one where the first step is a step of length $2$ feet. In the first case, there are $n-1$ feet left to cross, which by definition can be done in $P_{n-1}$ ways, and in the second case there are $n-2$ feet left to cross, which by definition can be done in $P_{n-2}$ ways
So, we have that:
$$P_n = P_{n-1}+P_{n-2}$$
and there is obviously your connection with the Fibonacci problem!
Now you just have to figure out what $P_1$ and and $P_2$ are, but that's trivial: $P_1=1$, and $P_2=2$
So, if we follow the convention that for the Fibonacci numbers we have that $F_1=F_2=1$, then we see that $P_1=F_2$, $P_2=F_3$, and thus in general that $P_n$=$F_{n+1}$
So, crossing this 12-foot bridge can be done in $P_{12}=F_{13}=233$ ways
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
answered Jan 28 at 23:24
Bram28Bram28
63.9k44793
63.9k44793
add a comment |
add a comment |
$begingroup$
You are correct that the result will be the Fibonacci sequence (with possible shifting depending on whether you start counting from zero or from one).
How I would explain it is that given a bridge of length $ngeq 2$ that he wants to traverse, he must either begin by taking a 1-foot step followed by some sequence of steps to traverse the remaining $n-1$ feet, or he begins by taking a 2-foot step followed by some sequence of steps to traverse the remaining $n-2$ feet. It is clear that these two cases cover all possibilities and do so with no overlap.
Letting $f(n)$ be the function counting the number of ways to traverse a bridge of length $n$, the above observation leads us to the familiar $f(n)=f(n-1)+f(n-2)$, here $f(n-1)$ counts the number of ways where you begin with a 1-foot step followed by a sequence of steps to traverse the remaining $n-1$ feet, and $f(n-2)$ counting the number of ways where you begin with a 2-foot step and traverse the remaining $n-2$ feet.
All that remains is to have some initial values. In this case, we need two consecutive values in order to give enough information to find all others. $f(1)=1$ should be clear. From here, you could either note that $f(2)=2$, or you could prefer to recognize that $f(0)=1$ as the empty sequence of steps still counts as a sequence of steps. Often-times by noting the existence of an empty-sequence or empty-string as a valid configuration implying that $f(0)=1$ (which is a relatively common occurrence for problems like these) this will help make finding a closed form much easier due to the nice properties of the numbers $0$ and $1$.
You see then that as the recurrence is the same as that of the Fibonacci sequence and the initial values are also the same, that this is indeed the Fibonacci sequence after all.
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
$endgroup$
add a comment |
$begingroup$
You are correct that the result will be the Fibonacci sequence (with possible shifting depending on whether you start counting from zero or from one).
How I would explain it is that given a bridge of length $ngeq 2$ that he wants to traverse, he must either begin by taking a 1-foot step followed by some sequence of steps to traverse the remaining $n-1$ feet, or he begins by taking a 2-foot step followed by some sequence of steps to traverse the remaining $n-2$ feet. It is clear that these two cases cover all possibilities and do so with no overlap.
Letting $f(n)$ be the function counting the number of ways to traverse a bridge of length $n$, the above observation leads us to the familiar $f(n)=f(n-1)+f(n-2)$, here $f(n-1)$ counts the number of ways where you begin with a 1-foot step followed by a sequence of steps to traverse the remaining $n-1$ feet, and $f(n-2)$ counting the number of ways where you begin with a 2-foot step and traverse the remaining $n-2$ feet.
All that remains is to have some initial values. In this case, we need two consecutive values in order to give enough information to find all others. $f(1)=1$ should be clear. From here, you could either note that $f(2)=2$, or you could prefer to recognize that $f(0)=1$ as the empty sequence of steps still counts as a sequence of steps. Often-times by noting the existence of an empty-sequence or empty-string as a valid configuration implying that $f(0)=1$ (which is a relatively common occurrence for problems like these) this will help make finding a closed form much easier due to the nice properties of the numbers $0$ and $1$.
You see then that as the recurrence is the same as that of the Fibonacci sequence and the initial values are also the same, that this is indeed the Fibonacci sequence after all.
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
$endgroup$
add a comment |
$begingroup$
You are correct that the result will be the Fibonacci sequence (with possible shifting depending on whether you start counting from zero or from one).
How I would explain it is that given a bridge of length $ngeq 2$ that he wants to traverse, he must either begin by taking a 1-foot step followed by some sequence of steps to traverse the remaining $n-1$ feet, or he begins by taking a 2-foot step followed by some sequence of steps to traverse the remaining $n-2$ feet. It is clear that these two cases cover all possibilities and do so with no overlap.
Letting $f(n)$ be the function counting the number of ways to traverse a bridge of length $n$, the above observation leads us to the familiar $f(n)=f(n-1)+f(n-2)$, here $f(n-1)$ counts the number of ways where you begin with a 1-foot step followed by a sequence of steps to traverse the remaining $n-1$ feet, and $f(n-2)$ counting the number of ways where you begin with a 2-foot step and traverse the remaining $n-2$ feet.
All that remains is to have some initial values. In this case, we need two consecutive values in order to give enough information to find all others. $f(1)=1$ should be clear. From here, you could either note that $f(2)=2$, or you could prefer to recognize that $f(0)=1$ as the empty sequence of steps still counts as a sequence of steps. Often-times by noting the existence of an empty-sequence or empty-string as a valid configuration implying that $f(0)=1$ (which is a relatively common occurrence for problems like these) this will help make finding a closed form much easier due to the nice properties of the numbers $0$ and $1$.
You see then that as the recurrence is the same as that of the Fibonacci sequence and the initial values are also the same, that this is indeed the Fibonacci sequence after all.
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
$endgroup$
You are correct that the result will be the Fibonacci sequence (with possible shifting depending on whether you start counting from zero or from one).
How I would explain it is that given a bridge of length $ngeq 2$ that he wants to traverse, he must either begin by taking a 1-foot step followed by some sequence of steps to traverse the remaining $n-1$ feet, or he begins by taking a 2-foot step followed by some sequence of steps to traverse the remaining $n-2$ feet. It is clear that these two cases cover all possibilities and do so with no overlap.
Letting $f(n)$ be the function counting the number of ways to traverse a bridge of length $n$, the above observation leads us to the familiar $f(n)=f(n-1)+f(n-2)$, here $f(n-1)$ counts the number of ways where you begin with a 1-foot step followed by a sequence of steps to traverse the remaining $n-1$ feet, and $f(n-2)$ counting the number of ways where you begin with a 2-foot step and traverse the remaining $n-2$ feet.
All that remains is to have some initial values. In this case, we need two consecutive values in order to give enough information to find all others. $f(1)=1$ should be clear. From here, you could either note that $f(2)=2$, or you could prefer to recognize that $f(0)=1$ as the empty sequence of steps still counts as a sequence of steps. Often-times by noting the existence of an empty-sequence or empty-string as a valid configuration implying that $f(0)=1$ (which is a relatively common occurrence for problems like these) this will help make finding a closed form much easier due to the nice properties of the numbers $0$ and $1$.
You see then that as the recurrence is the same as that of the Fibonacci sequence and the initial values are also the same, that this is indeed the Fibonacci sequence after all.
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
answered Jan 28 at 23:27
JMoravitzJMoravitz
48.7k43988
48.7k43988
add a comment |
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.
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%2f3091532%2fandrew-wants-to-cross-a-12-foot-long-bridge-he-can-either-take-a-1-foot-step-or%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
