What is the relation in this sequence












3












$begingroup$


I was attending a coding competition and this question came up



There is a box containing n chocolates. You can either take 1 chocolate or 3 chocolates at a time until its empty. So in total how many ways you can empty the chocolate for a given n.



Eg: n = 3



ways you can take out is 2 ie:



111

3


ways you can take out when n=4 is 3 ie:



1111

31

13


likewise, I have calculated manually for n=5 -> 4 etc etc..



so the result sequence comes up like 2,3,4,6,9...



I am not able to figure out what kind of relation it has or how do I solve it. I'm not able to figure out what kind of problem it is as well (Permutation, combinations, series?). let me know if I need to post any more details.






sequences-and-series permutations contest-math combinations







share|cite|improve this question









New contributor




Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    So you're looking at the number of positive integers solutions to $$ 3x + y = k $$ for a fixed value for $k$. Maybe something like this can help: math.stackexchange.com/questions/29019/… and handakafunda.com/…
    $endgroup$
    – Matti P.
    yesterday








  • 2




    $begingroup$
    @MattiP. I think $x,y$ should be non-negative integers, not be positive integers. And the order is also important. For example, if $k=4$, then $(x,y)=(1,1)$ or $(0,4)$. But in the case $(x,y)=(1,1)$, $31$ and $13$ is not the same way...
    $endgroup$
    – Doyun Nam
    yesterday










  • $begingroup$
    yes. the order is important.
    $endgroup$
    – Shobi
    yesterday










  • $begingroup$
    The OEIS is always available as a last (or first) resort. Entering your sequence 2, 3, 4, 6, 9 gives A000930 which includes lots of (potentially) useful stuff. The Formulas section may be of use to you.
    $endgroup$
    – Peter Phipps
    yesterday










  • $begingroup$
    Thanks, Peter. I actually tried some online sequence solutions, but they didn't gave me much of idea. but this one I am encountering it for the first time its super usefull
    $endgroup$
    – Shobi
    22 hours ago
















3












$begingroup$


I was attending a coding competition and this question came up



There is a box containing n chocolates. You can either take 1 chocolate or 3 chocolates at a time until its empty. So in total how many ways you can empty the chocolate for a given n.



Eg: n = 3



ways you can take out is 2 ie:



111

3


ways you can take out when n=4 is 3 ie:



1111

31

13


likewise, I have calculated manually for n=5 -> 4 etc etc..



so the result sequence comes up like 2,3,4,6,9...



I am not able to figure out what kind of relation it has or how do I solve it. I'm not able to figure out what kind of problem it is as well (Permutation, combinations, series?). let me know if I need to post any more details.






sequences-and-series permutations contest-math combinations







share|cite|improve this question









New contributor




Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    So you're looking at the number of positive integers solutions to $$ 3x + y = k $$ for a fixed value for $k$. Maybe something like this can help: math.stackexchange.com/questions/29019/… and handakafunda.com/…
    $endgroup$
    – Matti P.
    yesterday








  • 2




    $begingroup$
    @MattiP. I think $x,y$ should be non-negative integers, not be positive integers. And the order is also important. For example, if $k=4$, then $(x,y)=(1,1)$ or $(0,4)$. But in the case $(x,y)=(1,1)$, $31$ and $13$ is not the same way...
    $endgroup$
    – Doyun Nam
    yesterday










  • $begingroup$
    yes. the order is important.
    $endgroup$
    – Shobi
    yesterday










  • $begingroup$
    The OEIS is always available as a last (or first) resort. Entering your sequence 2, 3, 4, 6, 9 gives A000930 which includes lots of (potentially) useful stuff. The Formulas section may be of use to you.
    $endgroup$
    – Peter Phipps
    yesterday










  • $begingroup$
    Thanks, Peter. I actually tried some online sequence solutions, but they didn't gave me much of idea. but this one I am encountering it for the first time its super usefull
    $endgroup$
    – Shobi
    22 hours ago














3












3








3


3



$begingroup$


I was attending a coding competition and this question came up



There is a box containing n chocolates. You can either take 1 chocolate or 3 chocolates at a time until its empty. So in total how many ways you can empty the chocolate for a given n.



Eg: n = 3



ways you can take out is 2 ie:



111

3


ways you can take out when n=4 is 3 ie:



1111

31

13


likewise, I have calculated manually for n=5 -> 4 etc etc..



so the result sequence comes up like 2,3,4,6,9...



I am not able to figure out what kind of relation it has or how do I solve it. I'm not able to figure out what kind of problem it is as well (Permutation, combinations, series?). let me know if I need to post any more details.






sequences-and-series permutations contest-math combinations







share|cite|improve this question









New contributor




Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




I was attending a coding competition and this question came up



There is a box containing n chocolates. You can either take 1 chocolate or 3 chocolates at a time until its empty. So in total how many ways you can empty the chocolate for a given n.



Eg: n = 3



ways you can take out is 2 ie:



111

3


ways you can take out when n=4 is 3 ie:



1111

31

13


likewise, I have calculated manually for n=5 -> 4 etc etc..



so the result sequence comes up like 2,3,4,6,9...



I am not able to figure out what kind of relation it has or how do I solve it. I'm not able to figure out what kind of problem it is as well (Permutation, combinations, series?). let me know if I need to post any more details.






sequences-and-series permutations contest-math combinations




sequences-and-series permutations contest-math combinations






share|cite|improve this question









New contributor




Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited yesterday









YuiTo Cheng

746322




746322






New contributor




Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked yesterday









ShobiShobi

1185




1185




New contributor




Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Shobi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • $begingroup$
    So you're looking at the number of positive integers solutions to $$ 3x + y = k $$ for a fixed value for $k$. Maybe something like this can help: math.stackexchange.com/questions/29019/… and handakafunda.com/…
    $endgroup$
    – Matti P.
    yesterday








  • 2




    $begingroup$
    @MattiP. I think $x,y$ should be non-negative integers, not be positive integers. And the order is also important. For example, if $k=4$, then $(x,y)=(1,1)$ or $(0,4)$. But in the case $(x,y)=(1,1)$, $31$ and $13$ is not the same way...
    $endgroup$
    – Doyun Nam
    yesterday










  • $begingroup$
    yes. the order is important.
    $endgroup$
    – Shobi
    yesterday










  • $begingroup$
    The OEIS is always available as a last (or first) resort. Entering your sequence 2, 3, 4, 6, 9 gives A000930 which includes lots of (potentially) useful stuff. The Formulas section may be of use to you.
    $endgroup$
    – Peter Phipps
    yesterday










  • $begingroup$
    Thanks, Peter. I actually tried some online sequence solutions, but they didn't gave me much of idea. but this one I am encountering it for the first time its super usefull
    $endgroup$
    – Shobi
    22 hours ago


















  • $begingroup$
    So you're looking at the number of positive integers solutions to $$ 3x + y = k $$ for a fixed value for $k$. Maybe something like this can help: math.stackexchange.com/questions/29019/… and handakafunda.com/…
    $endgroup$
    – Matti P.
    yesterday








  • 2




    $begingroup$
    @MattiP. I think $x,y$ should be non-negative integers, not be positive integers. And the order is also important. For example, if $k=4$, then $(x,y)=(1,1)$ or $(0,4)$. But in the case $(x,y)=(1,1)$, $31$ and $13$ is not the same way...
    $endgroup$
    – Doyun Nam
    yesterday










  • $begingroup$
    yes. the order is important.
    $endgroup$
    – Shobi
    yesterday










  • $begingroup$
    The OEIS is always available as a last (or first) resort. Entering your sequence 2, 3, 4, 6, 9 gives A000930 which includes lots of (potentially) useful stuff. The Formulas section may be of use to you.
    $endgroup$
    – Peter Phipps
    yesterday










  • $begingroup$
    Thanks, Peter. I actually tried some online sequence solutions, but they didn't gave me much of idea. but this one I am encountering it for the first time its super usefull
    $endgroup$
    – Shobi
    22 hours ago
















$begingroup$
So you're looking at the number of positive integers solutions to $$ 3x + y = k $$ for a fixed value for $k$. Maybe something like this can help: math.stackexchange.com/questions/29019/… and handakafunda.com/…
$endgroup$
– Matti P.
yesterday






$begingroup$
So you're looking at the number of positive integers solutions to $$ 3x + y = k $$ for a fixed value for $k$. Maybe something like this can help: math.stackexchange.com/questions/29019/… and handakafunda.com/…
$endgroup$
– Matti P.
yesterday






2




2




$begingroup$
@MattiP. I think $x,y$ should be non-negative integers, not be positive integers. And the order is also important. For example, if $k=4$, then $(x,y)=(1,1)$ or $(0,4)$. But in the case $(x,y)=(1,1)$, $31$ and $13$ is not the same way...
$endgroup$
– Doyun Nam
yesterday




$begingroup$
@MattiP. I think $x,y$ should be non-negative integers, not be positive integers. And the order is also important. For example, if $k=4$, then $(x,y)=(1,1)$ or $(0,4)$. But in the case $(x,y)=(1,1)$, $31$ and $13$ is not the same way...
$endgroup$
– Doyun Nam
yesterday












$begingroup$
yes. the order is important.
$endgroup$
– Shobi
yesterday




$begingroup$
yes. the order is important.
$endgroup$
– Shobi
yesterday












$begingroup$
The OEIS is always available as a last (or first) resort. Entering your sequence 2, 3, 4, 6, 9 gives A000930 which includes lots of (potentially) useful stuff. The Formulas section may be of use to you.
$endgroup$
– Peter Phipps
yesterday




$begingroup$
The OEIS is always available as a last (or first) resort. Entering your sequence 2, 3, 4, 6, 9 gives A000930 which includes lots of (potentially) useful stuff. The Formulas section may be of use to you.
$endgroup$
– Peter Phipps
yesterday












$begingroup$
Thanks, Peter. I actually tried some online sequence solutions, but they didn't gave me much of idea. but this one I am encountering it for the first time its super usefull
$endgroup$
– Shobi
22 hours ago




$begingroup$
Thanks, Peter. I actually tried some online sequence solutions, but they didn't gave me much of idea. but this one I am encountering it for the first time its super usefull
$endgroup$
– Shobi
22 hours ago










2 Answers
2






active

oldest

votes


















3












$begingroup$

I think this problem is one of the problems related to recurrence relation.



Let $a_n$ be the number of ways.



For example, $a_1 =1$, $a_2 = 1$, $a_3=2$, $a_4=3$ as you mentioned above.




Let's think of the number of ways for $n$. Obviously, it is $a_n$.



If we take 1 chocolate at the first time, then the number of remaining chocolates is $n-1$.



And the number of ways for $n-1$ is $a_{n-1}$.



If we take 3 chocolate at the first time, then the number of remaining chocolates is $n-3$.



And the number of ways for $n-3$ is $a_{n-3}$.



Therefore, for $n geq 4$,



$$a_n = a_{n-1} + a_{n-3}.$$



The initial value is given as above.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    wonderful. I have calculated values till n=10 manually. and this formula seems to agree with our findings. Thanks man :)
    $endgroup$
    – Shobi
    yesterday



















6












$begingroup$

As we can take one or three, we have the recurrence



$$c_n=c_{n-1}+c_{n-3}$$



with the initial condition



$$c_2=c_1=c_0=1,$$ as with $n<3$ there is a single option.



It is an easy matter to program this using a recursive function, preferably with memoization. Anon-recursive solution is also possible and preferable, storing the values in an array.



C= [1, 1, 1]

for n in range(3, 20):

    C.append(C[n-1] + C[n-3])



1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872



Now let the roots of the caracteristic polynomial, $r^3-r^2-1$ be $r_0, r_1, overline r_1$ (there is a pair of conjugates). The general solution of the recurrence is



$$c_n=ar_0^n+br_1^n+overline boverline r_1^n,$$



where constants are determined by the system of equations



$$a+b+overline b=1,\ar_0+br_1+overline boverline r_1=1,\ar_0^2+br_1^2+overline boverline r_1^2=1.\$$



As one can check from the numerical values, the ratio of two successive terms quickly tends to the constant $1.465571231876768$, which is the real root (it has the largest modulus).



By numerical experimentation, it appears that the simple formula yields exact values in a large range:



$$c_n=[0.6114919919508175cdot1.465571231876768^n]$$



where the brackets denote rounding to the nearest integer.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Thanks for the code part :)
    $endgroup$
    – Shobi
    yesterday











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
});


}
});






Shobi is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3094710%2fwhat-is-the-relation-in-this-sequence%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









3












$begingroup$

I think this problem is one of the problems related to recurrence relation.



Let $a_n$ be the number of ways.



For example, $a_1 =1$, $a_2 = 1$, $a_3=2$, $a_4=3$ as you mentioned above.




Let's think of the number of ways for $n$. Obviously, it is $a_n$.



If we take 1 chocolate at the first time, then the number of remaining chocolates is $n-1$.



And the number of ways for $n-1$ is $a_{n-1}$.



If we take 3 chocolate at the first time, then the number of remaining chocolates is $n-3$.



And the number of ways for $n-3$ is $a_{n-3}$.



Therefore, for $n geq 4$,



$$a_n = a_{n-1} + a_{n-3}.$$



The initial value is given as above.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    wonderful. I have calculated values till n=10 manually. and this formula seems to agree with our findings. Thanks man :)
    $endgroup$
    – Shobi
    yesterday
















3












$begingroup$

I think this problem is one of the problems related to recurrence relation.



Let $a_n$ be the number of ways.



For example, $a_1 =1$, $a_2 = 1$, $a_3=2$, $a_4=3$ as you mentioned above.




Let's think of the number of ways for $n$. Obviously, it is $a_n$.



If we take 1 chocolate at the first time, then the number of remaining chocolates is $n-1$.



And the number of ways for $n-1$ is $a_{n-1}$.



If we take 3 chocolate at the first time, then the number of remaining chocolates is $n-3$.



And the number of ways for $n-3$ is $a_{n-3}$.



Therefore, for $n geq 4$,



$$a_n = a_{n-1} + a_{n-3}.$$



The initial value is given as above.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    wonderful. I have calculated values till n=10 manually. and this formula seems to agree with our findings. Thanks man :)
    $endgroup$
    – Shobi
    yesterday














3












3








3





$begingroup$

I think this problem is one of the problems related to recurrence relation.



Let $a_n$ be the number of ways.



For example, $a_1 =1$, $a_2 = 1$, $a_3=2$, $a_4=3$ as you mentioned above.




Let's think of the number of ways for $n$. Obviously, it is $a_n$.



If we take 1 chocolate at the first time, then the number of remaining chocolates is $n-1$.



And the number of ways for $n-1$ is $a_{n-1}$.



If we take 3 chocolate at the first time, then the number of remaining chocolates is $n-3$.



And the number of ways for $n-3$ is $a_{n-3}$.



Therefore, for $n geq 4$,



$$a_n = a_{n-1} + a_{n-3}.$$



The initial value is given as above.






share|cite|improve this answer











$endgroup$



I think this problem is one of the problems related to recurrence relation.



Let $a_n$ be the number of ways.



For example, $a_1 =1$, $a_2 = 1$, $a_3=2$, $a_4=3$ as you mentioned above.




Let's think of the number of ways for $n$. Obviously, it is $a_n$.



If we take 1 chocolate at the first time, then the number of remaining chocolates is $n-1$.



And the number of ways for $n-1$ is $a_{n-1}$.



If we take 3 chocolate at the first time, then the number of remaining chocolates is $n-3$.



And the number of ways for $n-3$ is $a_{n-3}$.



Therefore, for $n geq 4$,



$$a_n = a_{n-1} + a_{n-3}.$$



The initial value is given as above.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited yesterday

























answered yesterday









Doyun NamDoyun Nam

63619




63619








  • 1




    $begingroup$
    wonderful. I have calculated values till n=10 manually. and this formula seems to agree with our findings. Thanks man :)
    $endgroup$
    – Shobi
    yesterday














  • 1




    $begingroup$
    wonderful. I have calculated values till n=10 manually. and this formula seems to agree with our findings. Thanks man :)
    $endgroup$
    – Shobi
    yesterday








1




1




$begingroup$
wonderful. I have calculated values till n=10 manually. and this formula seems to agree with our findings. Thanks man :)
$endgroup$
– Shobi
yesterday




$begingroup$
wonderful. I have calculated values till n=10 manually. and this formula seems to agree with our findings. Thanks man :)
$endgroup$
– Shobi
yesterday











6












$begingroup$

As we can take one or three, we have the recurrence



$$c_n=c_{n-1}+c_{n-3}$$



with the initial condition



$$c_2=c_1=c_0=1,$$ as with $n<3$ there is a single option.



It is an easy matter to program this using a recursive function, preferably with memoization. Anon-recursive solution is also possible and preferable, storing the values in an array.



C= [1, 1, 1]

for n in range(3, 20):

    C.append(C[n-1] + C[n-3])



1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872



Now let the roots of the caracteristic polynomial, $r^3-r^2-1$ be $r_0, r_1, overline r_1$ (there is a pair of conjugates). The general solution of the recurrence is



$$c_n=ar_0^n+br_1^n+overline boverline r_1^n,$$



where constants are determined by the system of equations



$$a+b+overline b=1,\ar_0+br_1+overline boverline r_1=1,\ar_0^2+br_1^2+overline boverline r_1^2=1.\$$



As one can check from the numerical values, the ratio of two successive terms quickly tends to the constant $1.465571231876768$, which is the real root (it has the largest modulus).



By numerical experimentation, it appears that the simple formula yields exact values in a large range:



$$c_n=[0.6114919919508175cdot1.465571231876768^n]$$



where the brackets denote rounding to the nearest integer.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Thanks for the code part :)
    $endgroup$
    – Shobi
    yesterday
















6












$begingroup$

As we can take one or three, we have the recurrence



$$c_n=c_{n-1}+c_{n-3}$$



with the initial condition



$$c_2=c_1=c_0=1,$$ as with $n<3$ there is a single option.



It is an easy matter to program this using a recursive function, preferably with memoization. Anon-recursive solution is also possible and preferable, storing the values in an array.



C= [1, 1, 1]

for n in range(3, 20):

    C.append(C[n-1] + C[n-3])



1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872



Now let the roots of the caracteristic polynomial, $r^3-r^2-1$ be $r_0, r_1, overline r_1$ (there is a pair of conjugates). The general solution of the recurrence is



$$c_n=ar_0^n+br_1^n+overline boverline r_1^n,$$



where constants are determined by the system of equations



$$a+b+overline b=1,\ar_0+br_1+overline boverline r_1=1,\ar_0^2+br_1^2+overline boverline r_1^2=1.\$$



As one can check from the numerical values, the ratio of two successive terms quickly tends to the constant $1.465571231876768$, which is the real root (it has the largest modulus).



By numerical experimentation, it appears that the simple formula yields exact values in a large range:



$$c_n=[0.6114919919508175cdot1.465571231876768^n]$$



where the brackets denote rounding to the nearest integer.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Thanks for the code part :)
    $endgroup$
    – Shobi
    yesterday














6












6








6





$begingroup$

As we can take one or three, we have the recurrence



$$c_n=c_{n-1}+c_{n-3}$$



with the initial condition



$$c_2=c_1=c_0=1,$$ as with $n<3$ there is a single option.



It is an easy matter to program this using a recursive function, preferably with memoization. Anon-recursive solution is also possible and preferable, storing the values in an array.



C= [1, 1, 1]

for n in range(3, 20):

    C.append(C[n-1] + C[n-3])



1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872



Now let the roots of the caracteristic polynomial, $r^3-r^2-1$ be $r_0, r_1, overline r_1$ (there is a pair of conjugates). The general solution of the recurrence is



$$c_n=ar_0^n+br_1^n+overline boverline r_1^n,$$



where constants are determined by the system of equations



$$a+b+overline b=1,\ar_0+br_1+overline boverline r_1=1,\ar_0^2+br_1^2+overline boverline r_1^2=1.\$$



As one can check from the numerical values, the ratio of two successive terms quickly tends to the constant $1.465571231876768$, which is the real root (it has the largest modulus).



By numerical experimentation, it appears that the simple formula yields exact values in a large range:



$$c_n=[0.6114919919508175cdot1.465571231876768^n]$$



where the brackets denote rounding to the nearest integer.






share|cite|improve this answer











$endgroup$



As we can take one or three, we have the recurrence



$$c_n=c_{n-1}+c_{n-3}$$



with the initial condition



$$c_2=c_1=c_0=1,$$ as with $n<3$ there is a single option.



It is an easy matter to program this using a recursive function, preferably with memoization. Anon-recursive solution is also possible and preferable, storing the values in an array.



C= [1, 1, 1]

for n in range(3, 20):

    C.append(C[n-1] + C[n-3])



1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872



Now let the roots of the caracteristic polynomial, $r^3-r^2-1$ be $r_0, r_1, overline r_1$ (there is a pair of conjugates). The general solution of the recurrence is



$$c_n=ar_0^n+br_1^n+overline boverline r_1^n,$$



where constants are determined by the system of equations



$$a+b+overline b=1,\ar_0+br_1+overline boverline r_1=1,\ar_0^2+br_1^2+overline boverline r_1^2=1.\$$



As one can check from the numerical values, the ratio of two successive terms quickly tends to the constant $1.465571231876768$, which is the real root (it has the largest modulus).



By numerical experimentation, it appears that the simple formula yields exact values in a large range:



$$c_n=[0.6114919919508175cdot1.465571231876768^n]$$



where the brackets denote rounding to the nearest integer.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited yesterday

























answered yesterday









Yves DaoustYves Daoust

126k672226




126k672226












  • $begingroup$
    Thanks for the code part :)
    $endgroup$
    – Shobi
    yesterday


















  • $begingroup$
    Thanks for the code part :)
    $endgroup$
    – Shobi
    yesterday
















$begingroup$
Thanks for the code part :)
$endgroup$
– Shobi
yesterday




$begingroup$
Thanks for the code part :)
$endgroup$
– Shobi
yesterday










Shobi is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















Shobi is a new contributor. Be nice, and check out our Code of Conduct.













Shobi is a new contributor. Be nice, and check out our Code of Conduct.












Shobi is a new contributor. Be nice, and check out our Code of Conduct.
















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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3094710%2fwhat-is-the-relation-in-this-sequence%23new-answer', 'question_page');
}
);

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







-

Popular posts from this blog

If I really need a card on my start hand, how many mulligans make sense? [duplicate]

Image
5 This question already has an answer here: How do you calculate the likelihood of drawing certain cards in your opening hand? 3 answers There is a funny modern deck where you play Treasure Hunt, but you really need to have it on the starting hand. How many mulligans should I take, if my deck contains 60 cards and contains 4 copies of Treasure Hunt? magic-the-gathering probability share | improve this question asked Nov 23 '18 at 12:12 dan dan 152 4
Read more

Alcedinidae

Image
Alcedinidae Martin-pêcheur à dos bleu ( Alcedo azurea ) Classification (COI) Règne Animalia Embranchement Chordata Sous-embr. Vertebrata Classe Aves Ordre Coraciiformes Famille Alcedinidae Rafinesque, 1815 Les Alcédinidés ou Alcedinidae forment une famille d'oiseaux plus connus sous les noms de martins-pêcheurs et martins-chasseurs. Sommaire 1 Description 2 Répartition et habitat 3 Systématique 3.1 Liste alphabétique des genres 3.2 Liste des espèces 4 Chez les Anciens : l'alcyon 4.1 Étymologie (Littré) 4.2 Oiseau « fabuleux » ? 5 Notes 6 Articles connexes 7 Liens externes 7.1 Bibliographie Description | Ce sont des oiseaux compacts de taille petite à moyenne (10 à 46 cm), au bec droit et long, en forme de poignard. Leurs pattes sont courtes, et ils portent un plumage aux couleurs vives. Répartition et habitat | Cosmopolites, ils fréquentent surtout
Read more

Can an atomic nucleus contain both particles and antiparticles? [duplicate]

Image
9 $begingroup$ This question already has an answer here: What happens if we put together a proton and an antineutron? 2 answers Is it theoretically possible to make a "deuterium" atom containing a proton and an antineutron in its nucleus? Would the strong nuclear force cause attraction between a proton and an antineutron? Would such a nucleus be stable, or would the proton somehow annihilate the antineutron when close enough? nuclear-physics antimatter share | cite | improve this question asked yesterday
Read more