Recursion and Catalan Numbers
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Consider the sequence defined by
$$
begincases
r_0=1\
r_1=3\
r_n=6r_n-1-9r_n-2 & textif nge 2
endcases
.$$
Find a closed form for $r_n$.
Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.
I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?
catalan-numbers
add a comment |Â
up vote
2
down vote
favorite
Consider the sequence defined by
$$
begincases
r_0=1\
r_1=3\
r_n=6r_n-1-9r_n-2 & textif nge 2
endcases
.$$
Find a closed form for $r_n$.
Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.
I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?
catalan-numbers
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Consider the sequence defined by
$$
begincases
r_0=1\
r_1=3\
r_n=6r_n-1-9r_n-2 & textif nge 2
endcases
.$$
Find a closed form for $r_n$.
Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.
I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?
catalan-numbers
Consider the sequence defined by
$$
begincases
r_0=1\
r_1=3\
r_n=6r_n-1-9r_n-2 & textif nge 2
endcases
.$$
Find a closed form for $r_n$.
Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.
I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?
catalan-numbers
asked Aug 25 at 5:35
WolverineA03
1427
1427
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.
add a comment |Â
up vote
1
down vote
Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.
Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.
answered Aug 25 at 6:11
J.-E. Pin
17.5k21753
17.5k21753
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2893819%2frecursion-and-catalan-numbers%23new-answer', 'question_page');
);
Post as a guest
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
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
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