Solving Recurrence Relation for the number of n-letter words
Find and solve the recurrence relation for the number of n-letter words composed from letters A, B, C and D such that no A comes after any B.
What I learn in the class is,
$$ A = a_{n-1} $$
$$ B = 3^{n-1} $$
$$ C = a_{n-1} $$
$$ D = a_{n-1} $$
why B is different from other? Also how can I solve this one using recurrence relation? Thanks in advance!
discrete-mathematics recurrence-relations
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
add a comment |
Find and solve the recurrence relation for the number of n-letter words composed from letters A, B, C and D such that no A comes after any B.
What I learn in the class is,
$$ A = a_{n-1} $$
$$ B = 3^{n-1} $$
$$ C = a_{n-1} $$
$$ D = a_{n-1} $$
why B is different from other? Also how can I solve this one using recurrence relation? Thanks in advance!
discrete-mathematics recurrence-relations
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
add a comment |
Find and solve the recurrence relation for the number of n-letter words composed from letters A, B, C and D such that no A comes after any B.
What I learn in the class is,
$$ A = a_{n-1} $$
$$ B = 3^{n-1} $$
$$ C = a_{n-1} $$
$$ D = a_{n-1} $$
why B is different from other? Also how can I solve this one using recurrence relation? Thanks in advance!
discrete-mathematics recurrence-relations
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
Find and solve the recurrence relation for the number of n-letter words composed from letters A, B, C and D such that no A comes after any B.
What I learn in the class is,
$$ A = a_{n-1} $$
$$ B = 3^{n-1} $$
$$ C = a_{n-1} $$
$$ D = a_{n-1} $$
why B is different from other? Also how can I solve this one using recurrence relation? Thanks in advance!
discrete-mathematics recurrence-relations
discrete-mathematics recurrence-relations
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
edited Dec 9 '18 at 20:52
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
asked Dec 9 '18 at 20:37
jaykodeveloper
1258
1258
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
The difference for $B$ is because once we use a $B$, we can't have any $A$'s in the rest of the string (if we start with any other letter, then any good string works). I'm assuming the third line should be $C =a_{n-1}$, and that this means "the number of $n$-letter good strings starting with $C$ is $a_{n-1}$." This justification comes from the fact that, if we start with $C$ (or $A$ or $D$), then to make a good string, we just add on another good string of length $n-1$. But if we start with $B$, then we can't just add on a shorter good string because that might contain $A$; instead, we just want to count how many strings we can make that don't use $A$; this is just $3^{n-1}$.
Summing over all cases gives the recurrence relation $a_n = 3a_{n-1} + 3^{n-1}$.
answered Dec 9 '18 at 20:42
platty
3,360320
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%2f3032964%2fsolving-recurrence-relation-for-the-number-of-n-letter-words%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The difference for $B$ is because once we use a $B$, we can't have any $A$'s in the rest of the string (if we start with any other letter, then any good string works). I'm assuming the third line should be $C =a_{n-1}$, and that this means "the number of $n$-letter good strings starting with $C$ is $a_{n-1}$." This justification comes from the fact that, if we start with $C$ (or $A$ or $D$), then to make a good string, we just add on another good string of length $n-1$. But if we start with $B$, then we can't just add on a shorter good string because that might contain $A$; instead, we just want to count how many strings we can make that don't use $A$; this is just $3^{n-1}$.
Summing over all cases gives the recurrence relation $a_n = 3a_{n-1} + 3^{n-1}$.
answered Dec 9 '18 at 20:42
platty
3,360320
add a comment |
The difference for $B$ is because once we use a $B$, we can't have any $A$'s in the rest of the string (if we start with any other letter, then any good string works). I'm assuming the third line should be $C =a_{n-1}$, and that this means "the number of $n$-letter good strings starting with $C$ is $a_{n-1}$." This justification comes from the fact that, if we start with $C$ (or $A$ or $D$), then to make a good string, we just add on another good string of length $n-1$. But if we start with $B$, then we can't just add on a shorter good string because that might contain $A$; instead, we just want to count how many strings we can make that don't use $A$; this is just $3^{n-1}$.
Summing over all cases gives the recurrence relation $a_n = 3a_{n-1} + 3^{n-1}$.
answered Dec 9 '18 at 20:42
platty
3,360320
add a comment |
The difference for $B$ is because once we use a $B$, we can't have any $A$'s in the rest of the string (if we start with any other letter, then any good string works). I'm assuming the third line should be $C =a_{n-1}$, and that this means "the number of $n$-letter good strings starting with $C$ is $a_{n-1}$." This justification comes from the fact that, if we start with $C$ (or $A$ or $D$), then to make a good string, we just add on another good string of length $n-1$. But if we start with $B$, then we can't just add on a shorter good string because that might contain $A$; instead, we just want to count how many strings we can make that don't use $A$; this is just $3^{n-1}$.
Summing over all cases gives the recurrence relation $a_n = 3a_{n-1} + 3^{n-1}$.
answered Dec 9 '18 at 20:42
platty
3,360320
The difference for $B$ is because once we use a $B$, we can't have any $A$'s in the rest of the string (if we start with any other letter, then any good string works). I'm assuming the third line should be $C =a_{n-1}$, and that this means "the number of $n$-letter good strings starting with $C$ is $a_{n-1}$." This justification comes from the fact that, if we start with $C$ (or $A$ or $D$), then to make a good string, we just add on another good string of length $n-1$. But if we start with $B$, then we can't just add on a shorter good string because that might contain $A$; instead, we just want to count how many strings we can make that don't use $A$; this is just $3^{n-1}$.
Summing over all cases gives the recurrence relation $a_n = 3a_{n-1} + 3^{n-1}$.
answered Dec 9 '18 at 20:42
platty
3,360320
answered Dec 9 '18 at 20:42
platty
3,360320
answered Dec 9 '18 at 20:42
platty
3,360320
answered Dec 9 '18 at 20:42
platty
3,360320
3,360320
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.
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%2f3032964%2fsolving-recurrence-relation-for-the-number-of-n-letter-words%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
