Mixing
homogenous linear recurrence relation - need help with understanding the solution
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I apologize if this question is far too obvious, but I'm a bit confused (and new to this subject).
I have to solve the recurrence relation:
$a_n=6a_n-1-9a_n-2$
$n=2,3,..$
Using Euler substitution, I get
$x^2-6x-9=0$
Solving this equation gives me $x_1=x_2=3$
The solution seemed to be obvious (since there weren't any initial conditions, I cannot determine $lambda$ coefficients): $a_n=lambda_1*3^n$
But the official one from my book is: $a_n=lambda_1*3^n+lambda_2*n*3^n$
The only explanation I'm left with is "Along with $3^n$, it's obvious that $n*3^n$ is another solution as well, which gives us $a_n=lambda_1*3^n+lambda_2*n*3^n$.
If anyone understands how they got the second solution, I would really appreciate an explanation. I assume it's something really obvious, but I can't see it. If the question isn't clear, please point me to it since I'm not sure I've translated it properly.
recurrence-relations
asked Aug 2 at 19:16
frostpad
475
add a comment |Â
up vote
2
down vote
favorite
I apologize if this question is far too obvious, but I'm a bit confused (and new to this subject).
I have to solve the recurrence relation:
$a_n=6a_n-1-9a_n-2$
$n=2,3,..$
Using Euler substitution, I get
$x^2-6x-9=0$
Solving this equation gives me $x_1=x_2=3$
The solution seemed to be obvious (since there weren't any initial conditions, I cannot determine $lambda$ coefficients): $a_n=lambda_1*3^n$
But the official one from my book is: $a_n=lambda_1*3^n+lambda_2*n*3^n$
The only explanation I'm left with is "Along with $3^n$, it's obvious that $n*3^n$ is another solution as well, which gives us $a_n=lambda_1*3^n+lambda_2*n*3^n$.
If anyone understands how they got the second solution, I would really appreciate an explanation. I assume it's something really obvious, but I can't see it. If the question isn't clear, please point me to it since I'm not sure I've translated it properly.
recurrence-relations
asked Aug 2 at 19:16
frostpad
475
1
Take a look here: math.berkeley.edu/~arash/55/8_2.pdf
– Robert Z
Aug 2 at 19:20
Found it, thank you!
– frostpad
Aug 2 at 19:25
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I apologize if this question is far too obvious, but I'm a bit confused (and new to this subject).
I have to solve the recurrence relation:
$a_n=6a_n-1-9a_n-2$
$n=2,3,..$
Using Euler substitution, I get
$x^2-6x-9=0$
Solving this equation gives me $x_1=x_2=3$
The solution seemed to be obvious (since there weren't any initial conditions, I cannot determine $lambda$ coefficients): $a_n=lambda_1*3^n$
But the official one from my book is: $a_n=lambda_1*3^n+lambda_2*n*3^n$
The only explanation I'm left with is "Along with $3^n$, it's obvious that $n*3^n$ is another solution as well, which gives us $a_n=lambda_1*3^n+lambda_2*n*3^n$.
If anyone understands how they got the second solution, I would really appreciate an explanation. I assume it's something really obvious, but I can't see it. If the question isn't clear, please point me to it since I'm not sure I've translated it properly.
recurrence-relations
asked Aug 2 at 19:16
frostpad
475
I apologize if this question is far too obvious, but I'm a bit confused (and new to this subject).
I have to solve the recurrence relation:
$a_n=6a_n-1-9a_n-2$
$n=2,3,..$
Using Euler substitution, I get
$x^2-6x-9=0$
Solving this equation gives me $x_1=x_2=3$
The solution seemed to be obvious (since there weren't any initial conditions, I cannot determine $lambda$ coefficients): $a_n=lambda_1*3^n$
But the official one from my book is: $a_n=lambda_1*3^n+lambda_2*n*3^n$
The only explanation I'm left with is "Along with $3^n$, it's obvious that $n*3^n$ is another solution as well, which gives us $a_n=lambda_1*3^n+lambda_2*n*3^n$.
If anyone understands how they got the second solution, I would really appreciate an explanation. I assume it's something really obvious, but I can't see it. If the question isn't clear, please point me to it since I'm not sure I've translated it properly.
recurrence-relations
asked Aug 2 at 19:16
frostpad
475
edited Aug 2 at 19:21
asked Aug 2 at 19:16
frostpad
475
asked Aug 2 at 19:16
frostpad
475
asked Aug 2 at 19:16
frostpad
475
475
1
Take a look here: math.berkeley.edu/~arash/55/8_2.pdf
– Robert Z
Aug 2 at 19:20
Found it, thank you!
– frostpad
Aug 2 at 19:25
add a comment |Â
1
Take a look here: math.berkeley.edu/~arash/55/8_2.pdf
– Robert Z
Aug 2 at 19:20
Found it, thank you!
– frostpad
Aug 2 at 19:25
1
1
Take a look here: math.berkeley.edu/~arash/55/8_2.pdf
– Robert Z
Aug 2 at 19:20
Take a look here: math.berkeley.edu/~arash/55/8_2.pdf
– Robert Z
Aug 2 at 19:20
Found it, thank you!
– frostpad
Aug 2 at 19:25
Found it, thank you!
– frostpad
Aug 2 at 19:25
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
But the official one from my book is: $a_n=lambda_1 cdot 3^n+lambda_2 cdot n cdot 3^n$
That is indeed the general solution in the case of a root with multiplicity $2$, as is the case here since the characteristic polynomial is $(x-3)^2$.
You can verify that it works by direct substitution in the recurrence relation.
Or, for another way to derive it, divide both sides of the recurrence relation by $3^n$:
$$
fraca_n3^n = 2 cdot fraca_n-13^n-1 - fraca_n-23^n-2
$$
With $b_n = dfraca_n3^n$ the above can be written as $b_n=2 b_n-1-b_n-2 iff b_n-b_n-1=b_n-1-b_n-2$, in other words $b_n$ is an arithmetic progression, so $b_n = lambda_1 + lambda_2 cdot n$ for some $lambda_1,2$.
For the general case of roots with multiplicity $gt 2$ see for example this or that.
answered Aug 2 at 19:25
dxiv
53.7k64796
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
accepted
But the official one from my book is: $a_n=lambda_1 cdot 3^n+lambda_2 cdot n cdot 3^n$
That is indeed the general solution in the case of a root with multiplicity $2$, as is the case here since the characteristic polynomial is $(x-3)^2$.
You can verify that it works by direct substitution in the recurrence relation.
Or, for another way to derive it, divide both sides of the recurrence relation by $3^n$:
$$
fraca_n3^n = 2 cdot fraca_n-13^n-1 - fraca_n-23^n-2
$$
With $b_n = dfraca_n3^n$ the above can be written as $b_n=2 b_n-1-b_n-2 iff b_n-b_n-1=b_n-1-b_n-2$, in other words $b_n$ is an arithmetic progression, so $b_n = lambda_1 + lambda_2 cdot n$ for some $lambda_1,2$.
For the general case of roots with multiplicity $gt 2$ see for example this or that.
answered Aug 2 at 19:25
dxiv
53.7k64796
add a comment |Â
up vote
1
down vote
accepted
But the official one from my book is: $a_n=lambda_1 cdot 3^n+lambda_2 cdot n cdot 3^n$
That is indeed the general solution in the case of a root with multiplicity $2$, as is the case here since the characteristic polynomial is $(x-3)^2$.
You can verify that it works by direct substitution in the recurrence relation.
Or, for another way to derive it, divide both sides of the recurrence relation by $3^n$:
$$
fraca_n3^n = 2 cdot fraca_n-13^n-1 - fraca_n-23^n-2
$$
With $b_n = dfraca_n3^n$ the above can be written as $b_n=2 b_n-1-b_n-2 iff b_n-b_n-1=b_n-1-b_n-2$, in other words $b_n$ is an arithmetic progression, so $b_n = lambda_1 + lambda_2 cdot n$ for some $lambda_1,2$.
For the general case of roots with multiplicity $gt 2$ see for example this or that.
answered Aug 2 at 19:25
dxiv
53.7k64796
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
But the official one from my book is: $a_n=lambda_1 cdot 3^n+lambda_2 cdot n cdot 3^n$
That is indeed the general solution in the case of a root with multiplicity $2$, as is the case here since the characteristic polynomial is $(x-3)^2$.
You can verify that it works by direct substitution in the recurrence relation.
Or, for another way to derive it, divide both sides of the recurrence relation by $3^n$:
$$
fraca_n3^n = 2 cdot fraca_n-13^n-1 - fraca_n-23^n-2
$$
With $b_n = dfraca_n3^n$ the above can be written as $b_n=2 b_n-1-b_n-2 iff b_n-b_n-1=b_n-1-b_n-2$, in other words $b_n$ is an arithmetic progression, so $b_n = lambda_1 + lambda_2 cdot n$ for some $lambda_1,2$.
For the general case of roots with multiplicity $gt 2$ see for example this or that.
answered Aug 2 at 19:25
dxiv
53.7k64796
But the official one from my book is: $a_n=lambda_1 cdot 3^n+lambda_2 cdot n cdot 3^n$
That is indeed the general solution in the case of a root with multiplicity $2$, as is the case here since the characteristic polynomial is $(x-3)^2$.
You can verify that it works by direct substitution in the recurrence relation.
Or, for another way to derive it, divide both sides of the recurrence relation by $3^n$:
$$
fraca_n3^n = 2 cdot fraca_n-13^n-1 - fraca_n-23^n-2
$$
With $b_n = dfraca_n3^n$ the above can be written as $b_n=2 b_n-1-b_n-2 iff b_n-b_n-1=b_n-1-b_n-2$, in other words $b_n$ is an arithmetic progression, so $b_n = lambda_1 + lambda_2 cdot n$ for some $lambda_1,2$.
For the general case of roots with multiplicity $gt 2$ see for example this or that.
answered Aug 2 at 19:25
dxiv
53.7k64796
answered Aug 2 at 19:25
dxiv
53.7k64796
answered Aug 2 at 19:25
dxiv
53.7k64796
answered Aug 2 at 19:25
dxiv
53.7k64796
53.7k64796
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%2f2870406%2fhomogenous-linear-recurrence-relation-need-help-with-understanding-the-solutio%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
1
Take a look here: math.berkeley.edu/~arash/55/8_2.pdf
– Robert Z
Aug 2 at 19:20
Found it, thank you!
– frostpad
Aug 2 at 19:25