Solve recurrence for strings that do not contain the substring 101
Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2cdots8.$ Find a recurrence relation for $A_n$. What does the solution of that recurrence look like?
These are the solutions that I have found for calculations for $A_n$. $1, 4, 7, 12, 20, 32, 48, 96$.
I've calculated this by hand. But how I do find the recurrence? I see that 4, 7, 12, 30 are Fibonacci - 1, but not after or before that.
But I'm not sure how to do this or if this is even correct.
combinatorics discrete-mathematics recurrence-relations
asked Dec 9 at 11:54
ponikoli
366
|
show 1 more comment
Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2cdots8.$ Find a recurrence relation for $A_n$. What does the solution of that recurrence look like?
These are the solutions that I have found for calculations for $A_n$. $1, 4, 7, 12, 20, 32, 48, 96$.
I've calculated this by hand. But how I do find the recurrence? I see that 4, 7, 12, 30 are Fibonacci - 1, but not after or before that.
But I'm not sure how to do this or if this is even correct.
combinatorics discrete-mathematics recurrence-relations
asked Dec 9 at 11:54
ponikoli
366
I think your values may be counting the complement; those strings that DO contain $101$, no?
– lulu
Dec 9 at 12:09
Many similar questions have been asked on the site...this question for instance.
– lulu
Dec 9 at 12:10
You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those.
– Mike Earnest
Dec 9 at 17:12
Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence?
– ponikoli
Dec 10 at 19:15
Try to proceed similarly to this answer.
– Alex Ravsky
Dec 11 at 5:30
|
show 1 more comment
Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2cdots8.$ Find a recurrence relation for $A_n$. What does the solution of that recurrence look like?
These are the solutions that I have found for calculations for $A_n$. $1, 4, 7, 12, 20, 32, 48, 96$.
I've calculated this by hand. But how I do find the recurrence? I see that 4, 7, 12, 30 are Fibonacci - 1, but not after or before that.
But I'm not sure how to do this or if this is even correct.
combinatorics discrete-mathematics recurrence-relations
asked Dec 9 at 11:54
ponikoli
366
Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2cdots8.$ Find a recurrence relation for $A_n$. What does the solution of that recurrence look like?
These are the solutions that I have found for calculations for $A_n$. $1, 4, 7, 12, 20, 32, 48, 96$.
I've calculated this by hand. But how I do find the recurrence? I see that 4, 7, 12, 30 are Fibonacci - 1, but not after or before that.
But I'm not sure how to do this or if this is even correct.
combinatorics discrete-mathematics recurrence-relations
combinatorics discrete-mathematics recurrence-relations
asked Dec 9 at 11:54
ponikoli
366
asked Dec 9 at 11:54
ponikoli
366
edited Dec 10 at 19:14
asked Dec 9 at 11:54
ponikoli
366
asked Dec 9 at 11:54
ponikoli
366
asked Dec 9 at 11:54
ponikoli
366
366
I think your values may be counting the complement; those strings that DO contain $101$, no?
– lulu
Dec 9 at 12:09
Many similar questions have been asked on the site...this question for instance.
– lulu
Dec 9 at 12:10
You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those.
– Mike Earnest
Dec 9 at 17:12
Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence?
– ponikoli
Dec 10 at 19:15
Try to proceed similarly to this answer.
– Alex Ravsky
Dec 11 at 5:30
|
show 1 more comment
I think your values may be counting the complement; those strings that DO contain $101$, no?
– lulu
Dec 9 at 12:09
Many similar questions have been asked on the site...this question for instance.
– lulu
Dec 9 at 12:10
You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those.
– Mike Earnest
Dec 9 at 17:12
Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence?
– ponikoli
Dec 10 at 19:15
Try to proceed similarly to this answer.
– Alex Ravsky
Dec 11 at 5:30
I think your values may be counting the complement; those strings that DO contain $101$, no?
– lulu
Dec 9 at 12:09
I think your values may be counting the complement; those strings that DO contain $101$, no?
– lulu
Dec 9 at 12:09
Many similar questions have been asked on the site...this question for instance.
– lulu
Dec 9 at 12:10
Many similar questions have been asked on the site...this question for instance.
– lulu
Dec 9 at 12:10
You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those.
– Mike Earnest
Dec 9 at 17:12
You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those.
– Mike Earnest
Dec 9 at 17:12
Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence?
– ponikoli
Dec 10 at 19:15
Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence?
– ponikoli
Dec 10 at 19:15
Try to proceed similarly to this answer.
– Alex Ravsky
Dec 11 at 5:30
Try to proceed similarly to this answer.
– Alex Ravsky
Dec 11 at 5:30
|
show 1 more comment
active
oldest
votes
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%2f3032321%2fsolve-recurrence-for-strings-that-do-not-contain-the-substring-101%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3032321%2fsolve-recurrence-for-strings-that-do-not-contain-the-substring-101%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
I think your values may be counting the complement; those strings that DO contain $101$, no?
– lulu
Dec 9 at 12:09
Many similar questions have been asked on the site...this question for instance.
– lulu
Dec 9 at 12:10
You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those.
– Mike Earnest
Dec 9 at 17:12
Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence?
– ponikoli
Dec 10 at 19:15
Try to proceed similarly to this answer.
– Alex Ravsky
Dec 11 at 5:30