How to find a recurrence relation for counting the number of solutions?
$begingroup$
Consider the diophantine equation
$$x_1+3x_2+5x_3 = n$$
where $x_igeq 0$ and $ngeq 1.$
Let $P_n(1,3,5)$ denote the number of solutions to this equation. I want to express $P_n(1,3,5)$ in terms of $P_{1}(1,3,5), P_{2}(1,3,5),cdots, P_{n-1}(1,3,5).$
Here is what I observed:
If $(x_1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k$$
then $(x_1+1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+1$$
$(x_1,x_2+1,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+3$$
and $(x_1,x_2,x_3+1)$ is a solution to
$$x_1+3x_2+5x_3 = k+5.$$
But I don't know know how to combine this to get the desired relation. Any ideas will be much appreciated.
Edit: Based on the answer given below, we observe that a solution (x_1,x_2,x_3) to
$$x_1+3x_2+5x_3 = n$$
must have $x_1>0$ or $x_2>0$ or $x_3>0.$ If $x_1>0$ then (x_1-1,x_2,x_3) is a solution
$$x_1+3x_2+5x_3 = n-1$$
and there are $P_{n-1}(1,3,5).$ Proceeding in a similar manner for $x_2$ and $x_3$ and applying the inclusion-exclusion principle we get:
$$P_{n}(1,3,5) = P_{n-1}(1,3,5)+P_{n-3}(1,3,5)+P_{n-5}(1,3,5)-P_{n-4}(1,3,5)-P_{n-8}(1,3,5)-P_{n-6}(1,3,5)+P_{n-9}(1,3,5).$$
number-theory elementary-set-theory diophantine-equations linear-diophantine-equations
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
$endgroup$
add a comment |
$begingroup$
Consider the diophantine equation
$$x_1+3x_2+5x_3 = n$$
where $x_igeq 0$ and $ngeq 1.$
Let $P_n(1,3,5)$ denote the number of solutions to this equation. I want to express $P_n(1,3,5)$ in terms of $P_{1}(1,3,5), P_{2}(1,3,5),cdots, P_{n-1}(1,3,5).$
Here is what I observed:
If $(x_1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k$$
then $(x_1+1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+1$$
$(x_1,x_2+1,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+3$$
and $(x_1,x_2,x_3+1)$ is a solution to
$$x_1+3x_2+5x_3 = k+5.$$
But I don't know know how to combine this to get the desired relation. Any ideas will be much appreciated.
Edit: Based on the answer given below, we observe that a solution (x_1,x_2,x_3) to
$$x_1+3x_2+5x_3 = n$$
must have $x_1>0$ or $x_2>0$ or $x_3>0.$ If $x_1>0$ then (x_1-1,x_2,x_3) is a solution
$$x_1+3x_2+5x_3 = n-1$$
and there are $P_{n-1}(1,3,5).$ Proceeding in a similar manner for $x_2$ and $x_3$ and applying the inclusion-exclusion principle we get:
$$P_{n}(1,3,5) = P_{n-1}(1,3,5)+P_{n-3}(1,3,5)+P_{n-5}(1,3,5)-P_{n-4}(1,3,5)-P_{n-8}(1,3,5)-P_{n-6}(1,3,5)+P_{n-9}(1,3,5).$$
number-theory elementary-set-theory diophantine-equations linear-diophantine-equations
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
$endgroup$
add a comment |
$begingroup$
Consider the diophantine equation
$$x_1+3x_2+5x_3 = n$$
where $x_igeq 0$ and $ngeq 1.$
Let $P_n(1,3,5)$ denote the number of solutions to this equation. I want to express $P_n(1,3,5)$ in terms of $P_{1}(1,3,5), P_{2}(1,3,5),cdots, P_{n-1}(1,3,5).$
Here is what I observed:
If $(x_1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k$$
then $(x_1+1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+1$$
$(x_1,x_2+1,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+3$$
and $(x_1,x_2,x_3+1)$ is a solution to
$$x_1+3x_2+5x_3 = k+5.$$
But I don't know know how to combine this to get the desired relation. Any ideas will be much appreciated.
Edit: Based on the answer given below, we observe that a solution (x_1,x_2,x_3) to
$$x_1+3x_2+5x_3 = n$$
must have $x_1>0$ or $x_2>0$ or $x_3>0.$ If $x_1>0$ then (x_1-1,x_2,x_3) is a solution
$$x_1+3x_2+5x_3 = n-1$$
and there are $P_{n-1}(1,3,5).$ Proceeding in a similar manner for $x_2$ and $x_3$ and applying the inclusion-exclusion principle we get:
$$P_{n}(1,3,5) = P_{n-1}(1,3,5)+P_{n-3}(1,3,5)+P_{n-5}(1,3,5)-P_{n-4}(1,3,5)-P_{n-8}(1,3,5)-P_{n-6}(1,3,5)+P_{n-9}(1,3,5).$$
number-theory elementary-set-theory diophantine-equations linear-diophantine-equations
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
$endgroup$
Consider the diophantine equation
$$x_1+3x_2+5x_3 = n$$
where $x_igeq 0$ and $ngeq 1.$
Let $P_n(1,3,5)$ denote the number of solutions to this equation. I want to express $P_n(1,3,5)$ in terms of $P_{1}(1,3,5), P_{2}(1,3,5),cdots, P_{n-1}(1,3,5).$
Here is what I observed:
If $(x_1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k$$
then $(x_1+1,x_2,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+1$$
$(x_1,x_2+1,x_3)$ is a solution to
$$x_1+3x_2+5x_3 = k+3$$
and $(x_1,x_2,x_3+1)$ is a solution to
$$x_1+3x_2+5x_3 = k+5.$$
But I don't know know how to combine this to get the desired relation. Any ideas will be much appreciated.
Edit: Based on the answer given below, we observe that a solution (x_1,x_2,x_3) to
$$x_1+3x_2+5x_3 = n$$
must have $x_1>0$ or $x_2>0$ or $x_3>0.$ If $x_1>0$ then (x_1-1,x_2,x_3) is a solution
$$x_1+3x_2+5x_3 = n-1$$
and there are $P_{n-1}(1,3,5).$ Proceeding in a similar manner for $x_2$ and $x_3$ and applying the inclusion-exclusion principle we get:
$$P_{n}(1,3,5) = P_{n-1}(1,3,5)+P_{n-3}(1,3,5)+P_{n-5}(1,3,5)-P_{n-4}(1,3,5)-P_{n-8}(1,3,5)-P_{n-6}(1,3,5)+P_{n-9}(1,3,5).$$
number-theory elementary-set-theory diophantine-equations linear-diophantine-equations
number-theory elementary-set-theory diophantine-equations linear-diophantine-equations
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
edited Jan 11 at 5:52
Hello_World
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
asked Jan 11 at 5:20
Hello_WorldHello_World
4,12621731
4,12621731
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let's do a simpler example: $P_n(2,3)$, the number of solutions to $2x+3y=n$
in nonnegative integers. For $n>0$ a solution must have either $x>0$ or $y>0$.
A solution with $x>0$ means that $(x-1,y)$ is a solution to $2X+3Y=n-2$
so there are $P_{n-2}(2,3)$ of these. Likewise there are $P_{n-3}(2,3)$
solutions with $y>0$. But some solutions have $x>0$ and $y>0$, and there
are $P_{n-5}(2,3)$ of these. By the inclusion/exclusion principle,
$$P_n(2,3)=P_{n-2}(2,3)+P_{n-3}(2,3)-P_{n-5}(2,3).$$
In your example, you'll have to do three-fold inclusion/exclusion...
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
$endgroup$
$begingroup$
I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct?
$endgroup$
– Hello_World
Jan 11 at 5:54
$begingroup$
Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World
$endgroup$
– Lord Shark the Unknown
Jan 11 at 5:56
$begingroup$
Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like.
$endgroup$
– Hello_World
Jan 11 at 6:00
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%2f3069497%2fhow-to-find-a-recurrence-relation-for-counting-the-number-of-solutions%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
$begingroup$
Let's do a simpler example: $P_n(2,3)$, the number of solutions to $2x+3y=n$
in nonnegative integers. For $n>0$ a solution must have either $x>0$ or $y>0$.
A solution with $x>0$ means that $(x-1,y)$ is a solution to $2X+3Y=n-2$
so there are $P_{n-2}(2,3)$ of these. Likewise there are $P_{n-3}(2,3)$
solutions with $y>0$. But some solutions have $x>0$ and $y>0$, and there
are $P_{n-5}(2,3)$ of these. By the inclusion/exclusion principle,
$$P_n(2,3)=P_{n-2}(2,3)+P_{n-3}(2,3)-P_{n-5}(2,3).$$
In your example, you'll have to do three-fold inclusion/exclusion...
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
$endgroup$
$begingroup$
I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct?
$endgroup$
– Hello_World
Jan 11 at 5:54
$begingroup$
Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World
$endgroup$
– Lord Shark the Unknown
Jan 11 at 5:56
$begingroup$
Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like.
$endgroup$
– Hello_World
Jan 11 at 6:00
add a comment |
$begingroup$
Let's do a simpler example: $P_n(2,3)$, the number of solutions to $2x+3y=n$
in nonnegative integers. For $n>0$ a solution must have either $x>0$ or $y>0$.
A solution with $x>0$ means that $(x-1,y)$ is a solution to $2X+3Y=n-2$
so there are $P_{n-2}(2,3)$ of these. Likewise there are $P_{n-3}(2,3)$
solutions with $y>0$. But some solutions have $x>0$ and $y>0$, and there
are $P_{n-5}(2,3)$ of these. By the inclusion/exclusion principle,
$$P_n(2,3)=P_{n-2}(2,3)+P_{n-3}(2,3)-P_{n-5}(2,3).$$
In your example, you'll have to do three-fold inclusion/exclusion...
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
$endgroup$
$begingroup$
I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct?
$endgroup$
– Hello_World
Jan 11 at 5:54
$begingroup$
Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World
$endgroup$
– Lord Shark the Unknown
Jan 11 at 5:56
$begingroup$
Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like.
$endgroup$
– Hello_World
Jan 11 at 6:00
add a comment |
$begingroup$
Let's do a simpler example: $P_n(2,3)$, the number of solutions to $2x+3y=n$
in nonnegative integers. For $n>0$ a solution must have either $x>0$ or $y>0$.
A solution with $x>0$ means that $(x-1,y)$ is a solution to $2X+3Y=n-2$
so there are $P_{n-2}(2,3)$ of these. Likewise there are $P_{n-3}(2,3)$
solutions with $y>0$. But some solutions have $x>0$ and $y>0$, and there
are $P_{n-5}(2,3)$ of these. By the inclusion/exclusion principle,
$$P_n(2,3)=P_{n-2}(2,3)+P_{n-3}(2,3)-P_{n-5}(2,3).$$
In your example, you'll have to do three-fold inclusion/exclusion...
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
$endgroup$
Let's do a simpler example: $P_n(2,3)$, the number of solutions to $2x+3y=n$
in nonnegative integers. For $n>0$ a solution must have either $x>0$ or $y>0$.
A solution with $x>0$ means that $(x-1,y)$ is a solution to $2X+3Y=n-2$
so there are $P_{n-2}(2,3)$ of these. Likewise there are $P_{n-3}(2,3)$
solutions with $y>0$. But some solutions have $x>0$ and $y>0$, and there
are $P_{n-5}(2,3)$ of these. By the inclusion/exclusion principle,
$$P_n(2,3)=P_{n-2}(2,3)+P_{n-3}(2,3)-P_{n-5}(2,3).$$
In your example, you'll have to do three-fold inclusion/exclusion...
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
answered Jan 11 at 5:31
Lord Shark the UnknownLord Shark the Unknown
103k1160132
103k1160132
$begingroup$
I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct?
$endgroup$
– Hello_World
Jan 11 at 5:54
$begingroup$
Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World
$endgroup$
– Lord Shark the Unknown
Jan 11 at 5:56
$begingroup$
Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like.
$endgroup$
– Hello_World
Jan 11 at 6:00
add a comment |
$begingroup$
I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct?
$endgroup$
– Hello_World
Jan 11 at 5:54
$begingroup$
Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World
$endgroup$
– Lord Shark the Unknown
Jan 11 at 5:56
$begingroup$
Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like.
$endgroup$
– Hello_World
Jan 11 at 6:00
$begingroup$
I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct?
$endgroup$
– Hello_World
Jan 11 at 5:54
$begingroup$
I have two questions: when $x>0$ and $y>0$ then if $(x-1,y-1)$ is a solution to $2x+3y=n-5$ and that is why there are $P_{n-5}(2,3)$ of them, right? And second, I made an edit. Do you think that the recurrence is correct?
$endgroup$
– Hello_World
Jan 11 at 5:54
$begingroup$
Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World
$endgroup$
– Lord Shark the Unknown
Jan 11 at 5:56
$begingroup$
Yes, and yes. Now, a better way to do all this is to use generating functions.... @Hello_World
$endgroup$
– Lord Shark the Unknown
Jan 11 at 5:56
$begingroup$
Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like.
$endgroup$
– Hello_World
Jan 11 at 6:00
$begingroup$
Yeah, I know for $P_n(2,3)$ we want the n'th coefficient of $$frac{1}{(1-x^2)(1-x^3)}.$$ But it's not clear what the power series looks like.
$endgroup$
– Hello_World
Jan 11 at 6:00
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%2f3069497%2fhow-to-find-a-recurrence-relation-for-counting-the-number-of-solutions%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
