Mixing
Is there a rule behind why $left 1+(-1/2)^n) right ^+infty_n=1$ is $a_n+2=1/2(a_n+1+a_n) , a_0 = 2 , a_1=1/2$ in recursive form?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I understand that both expresions represent the same sequence of numbers. It starts at $a_0=2$ and oscilate around 1 converging to it from up and down.
I have been playing around with the explicit form and I understand how to pass from $left (-1/2)^n) right ^+infty_n=1$ to $a_n=a_n-1(-1/2)^n, a_0=1$ that is the same sequence but shifted 1 unit up.
So, it seems that adding one unit to the sequence makes things more complicated when expresing it in recursive form.
My question is, what is the path of thought that someone can use to go from the explicit form $left 1+(-1/2)^n) right ^+infty_n=1$ to reach the recursive form $a_n+2=1/2(a_n+1+a_n) , a_0 = 2 , a_1=1/2$?
I´m looking for a way to understand why adding 1 to the sequence $left (-1/2)^n) right ^+infty_n=1$ generates the need to express the recursive form of the nth term in function of n-1 and n-2, in order to be able to recognize that need when analyzing similar sequences.
sequences-and-series closed-form recursive-algorithms
asked Jul 25 at 4:05
WalquerX
225
add a comment |Â
up vote
0
down vote
favorite
I understand that both expresions represent the same sequence of numbers. It starts at $a_0=2$ and oscilate around 1 converging to it from up and down.
I have been playing around with the explicit form and I understand how to pass from $left (-1/2)^n) right ^+infty_n=1$ to $a_n=a_n-1(-1/2)^n, a_0=1$ that is the same sequence but shifted 1 unit up.
So, it seems that adding one unit to the sequence makes things more complicated when expresing it in recursive form.
My question is, what is the path of thought that someone can use to go from the explicit form $left 1+(-1/2)^n) right ^+infty_n=1$ to reach the recursive form $a_n+2=1/2(a_n+1+a_n) , a_0 = 2 , a_1=1/2$?
I´m looking for a way to understand why adding 1 to the sequence $left (-1/2)^n) right ^+infty_n=1$ generates the need to express the recursive form of the nth term in function of n-1 and n-2, in order to be able to recognize that need when analyzing similar sequences.
sequences-and-series closed-form recursive-algorithms
asked Jul 25 at 4:05
WalquerX
225
1
You are dealing with a homogenous recurrence, which can be solved using characteristic polynomials, have a look at this answer as an example ... apply the same technique, but be careful, you have difference initial conditions.
– rtybase
Jul 25 at 7:42
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I understand that both expresions represent the same sequence of numbers. It starts at $a_0=2$ and oscilate around 1 converging to it from up and down.
I have been playing around with the explicit form and I understand how to pass from $left (-1/2)^n) right ^+infty_n=1$ to $a_n=a_n-1(-1/2)^n, a_0=1$ that is the same sequence but shifted 1 unit up.
So, it seems that adding one unit to the sequence makes things more complicated when expresing it in recursive form.
My question is, what is the path of thought that someone can use to go from the explicit form $left 1+(-1/2)^n) right ^+infty_n=1$ to reach the recursive form $a_n+2=1/2(a_n+1+a_n) , a_0 = 2 , a_1=1/2$?
I´m looking for a way to understand why adding 1 to the sequence $left (-1/2)^n) right ^+infty_n=1$ generates the need to express the recursive form of the nth term in function of n-1 and n-2, in order to be able to recognize that need when analyzing similar sequences.
sequences-and-series closed-form recursive-algorithms
asked Jul 25 at 4:05
WalquerX
225
I understand that both expresions represent the same sequence of numbers. It starts at $a_0=2$ and oscilate around 1 converging to it from up and down.
I have been playing around with the explicit form and I understand how to pass from $left (-1/2)^n) right ^+infty_n=1$ to $a_n=a_n-1(-1/2)^n, a_0=1$ that is the same sequence but shifted 1 unit up.
So, it seems that adding one unit to the sequence makes things more complicated when expresing it in recursive form.
My question is, what is the path of thought that someone can use to go from the explicit form $left 1+(-1/2)^n) right ^+infty_n=1$ to reach the recursive form $a_n+2=1/2(a_n+1+a_n) , a_0 = 2 , a_1=1/2$?
I´m looking for a way to understand why adding 1 to the sequence $left (-1/2)^n) right ^+infty_n=1$ generates the need to express the recursive form of the nth term in function of n-1 and n-2, in order to be able to recognize that need when analyzing similar sequences.
sequences-and-series closed-form recursive-algorithms
asked Jul 25 at 4:05
WalquerX
225
edited Jul 25 at 4:11
asked Jul 25 at 4:05
WalquerX
225
asked Jul 25 at 4:05
WalquerX
225
asked Jul 25 at 4:05
WalquerX
225
225
1
You are dealing with a homogenous recurrence, which can be solved using characteristic polynomials, have a look at this answer as an example ... apply the same technique, but be careful, you have difference initial conditions.
– rtybase
Jul 25 at 7:42
add a comment |Â
1
You are dealing with a homogenous recurrence, which can be solved using characteristic polynomials, have a look at this answer as an example ... apply the same technique, but be careful, you have difference initial conditions.
– rtybase
Jul 25 at 7:42
1
1
You are dealing with a homogenous recurrence, which can be solved using characteristic polynomials, have a look at this answer as an example ... apply the same technique, but be careful, you have difference initial conditions.
– rtybase
Jul 25 at 7:42
You are dealing with a homogenous recurrence, which can be solved using characteristic polynomials, have a look at this answer as an example ... apply the same technique, but be careful, you have difference initial conditions.
– rtybase
Jul 25 at 7:42
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
In general, a recursion of the form $a_n = k a_n-1$ has solution given by $a_n = A k^n$ while a recursion of the form $a_n = k_1 a_n-1 + k_2 a_n-2$ has solution given by $a_n = A c_1^n + B c_2^n$ (or, under certain circumstances, $(n+B) c_1^n$). So, since the sequence you're looking for has two exponential terms ($c_1 = 1$), a second order recurrence might be useful. For more information, you might like to read about linear recurrence relations.
For another perspective, consider $a_n = 1 + left(-frac12right)^n$, and our aim is to remove the dependence on $n$ on the right hand side with the help of $a_n-1$ and possibly $a_n-2$. So, we try considering $a_n - 1 = left(-frac12right)^n$ and noticing that $a_n-1 - 1 = left(-frac12right)^n-1$ so $-frac12left(a_n-1 - 1right) = left(-frac12right)^n$. Matching the right hand sides, we get $2(a_n - 1) = 1 - a_n-1$ so $2a_n - 2 = 1 - a_n-1$ and the recurrence $2a_n +a_n-1= 3$ i.e. $a_n = frac3 - a_n-12$, so the extra $a_n-2$ wasn't required.
But, this isn't a linear recurrence any more, and perhaps we'd like to make it linear. This is easily done by noticing $2a_n-1 +a_n-2= 3$ also, so
$$2a_n + a_n-1 = 2a_n-1 + a_n-2 implies a_n = frac12left(a_n-1 + a_n-2right).$$
answered Jul 25 at 4:20
B. Mehta
11.7k21944
In the first paragraph, is not $c_1=1?$
– WalquerX
Jul 26 at 12:30
Yup, fixed. My mistake.
– B. Mehta
Jul 26 at 17:12
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
In general, a recursion of the form $a_n = k a_n-1$ has solution given by $a_n = A k^n$ while a recursion of the form $a_n = k_1 a_n-1 + k_2 a_n-2$ has solution given by $a_n = A c_1^n + B c_2^n$ (or, under certain circumstances, $(n+B) c_1^n$). So, since the sequence you're looking for has two exponential terms ($c_1 = 1$), a second order recurrence might be useful. For more information, you might like to read about linear recurrence relations.
For another perspective, consider $a_n = 1 + left(-frac12right)^n$, and our aim is to remove the dependence on $n$ on the right hand side with the help of $a_n-1$ and possibly $a_n-2$. So, we try considering $a_n - 1 = left(-frac12right)^n$ and noticing that $a_n-1 - 1 = left(-frac12right)^n-1$ so $-frac12left(a_n-1 - 1right) = left(-frac12right)^n$. Matching the right hand sides, we get $2(a_n - 1) = 1 - a_n-1$ so $2a_n - 2 = 1 - a_n-1$ and the recurrence $2a_n +a_n-1= 3$ i.e. $a_n = frac3 - a_n-12$, so the extra $a_n-2$ wasn't required.
But, this isn't a linear recurrence any more, and perhaps we'd like to make it linear. This is easily done by noticing $2a_n-1 +a_n-2= 3$ also, so
$$2a_n + a_n-1 = 2a_n-1 + a_n-2 implies a_n = frac12left(a_n-1 + a_n-2right).$$
answered Jul 25 at 4:20
B. Mehta
11.7k21944
In the first paragraph, is not $c_1=1?$
– WalquerX
Jul 26 at 12:30
Yup, fixed. My mistake.
– B. Mehta
Jul 26 at 17:12
add a comment |Â
up vote
1
down vote
accepted
In general, a recursion of the form $a_n = k a_n-1$ has solution given by $a_n = A k^n$ while a recursion of the form $a_n = k_1 a_n-1 + k_2 a_n-2$ has solution given by $a_n = A c_1^n + B c_2^n$ (or, under certain circumstances, $(n+B) c_1^n$). So, since the sequence you're looking for has two exponential terms ($c_1 = 1$), a second order recurrence might be useful. For more information, you might like to read about linear recurrence relations.
For another perspective, consider $a_n = 1 + left(-frac12right)^n$, and our aim is to remove the dependence on $n$ on the right hand side with the help of $a_n-1$ and possibly $a_n-2$. So, we try considering $a_n - 1 = left(-frac12right)^n$ and noticing that $a_n-1 - 1 = left(-frac12right)^n-1$ so $-frac12left(a_n-1 - 1right) = left(-frac12right)^n$. Matching the right hand sides, we get $2(a_n - 1) = 1 - a_n-1$ so $2a_n - 2 = 1 - a_n-1$ and the recurrence $2a_n +a_n-1= 3$ i.e. $a_n = frac3 - a_n-12$, so the extra $a_n-2$ wasn't required.
But, this isn't a linear recurrence any more, and perhaps we'd like to make it linear. This is easily done by noticing $2a_n-1 +a_n-2= 3$ also, so
$$2a_n + a_n-1 = 2a_n-1 + a_n-2 implies a_n = frac12left(a_n-1 + a_n-2right).$$
answered Jul 25 at 4:20
B. Mehta
11.7k21944
In the first paragraph, is not $c_1=1?$
– WalquerX
Jul 26 at 12:30
Yup, fixed. My mistake.
– B. Mehta
Jul 26 at 17:12
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
In general, a recursion of the form $a_n = k a_n-1$ has solution given by $a_n = A k^n$ while a recursion of the form $a_n = k_1 a_n-1 + k_2 a_n-2$ has solution given by $a_n = A c_1^n + B c_2^n$ (or, under certain circumstances, $(n+B) c_1^n$). So, since the sequence you're looking for has two exponential terms ($c_1 = 1$), a second order recurrence might be useful. For more information, you might like to read about linear recurrence relations.
For another perspective, consider $a_n = 1 + left(-frac12right)^n$, and our aim is to remove the dependence on $n$ on the right hand side with the help of $a_n-1$ and possibly $a_n-2$. So, we try considering $a_n - 1 = left(-frac12right)^n$ and noticing that $a_n-1 - 1 = left(-frac12right)^n-1$ so $-frac12left(a_n-1 - 1right) = left(-frac12right)^n$. Matching the right hand sides, we get $2(a_n - 1) = 1 - a_n-1$ so $2a_n - 2 = 1 - a_n-1$ and the recurrence $2a_n +a_n-1= 3$ i.e. $a_n = frac3 - a_n-12$, so the extra $a_n-2$ wasn't required.
But, this isn't a linear recurrence any more, and perhaps we'd like to make it linear. This is easily done by noticing $2a_n-1 +a_n-2= 3$ also, so
$$2a_n + a_n-1 = 2a_n-1 + a_n-2 implies a_n = frac12left(a_n-1 + a_n-2right).$$
answered Jul 25 at 4:20
B. Mehta
11.7k21944
In general, a recursion of the form $a_n = k a_n-1$ has solution given by $a_n = A k^n$ while a recursion of the form $a_n = k_1 a_n-1 + k_2 a_n-2$ has solution given by $a_n = A c_1^n + B c_2^n$ (or, under certain circumstances, $(n+B) c_1^n$). So, since the sequence you're looking for has two exponential terms ($c_1 = 1$), a second order recurrence might be useful. For more information, you might like to read about linear recurrence relations.
For another perspective, consider $a_n = 1 + left(-frac12right)^n$, and our aim is to remove the dependence on $n$ on the right hand side with the help of $a_n-1$ and possibly $a_n-2$. So, we try considering $a_n - 1 = left(-frac12right)^n$ and noticing that $a_n-1 - 1 = left(-frac12right)^n-1$ so $-frac12left(a_n-1 - 1right) = left(-frac12right)^n$. Matching the right hand sides, we get $2(a_n - 1) = 1 - a_n-1$ so $2a_n - 2 = 1 - a_n-1$ and the recurrence $2a_n +a_n-1= 3$ i.e. $a_n = frac3 - a_n-12$, so the extra $a_n-2$ wasn't required.
But, this isn't a linear recurrence any more, and perhaps we'd like to make it linear. This is easily done by noticing $2a_n-1 +a_n-2= 3$ also, so
$$2a_n + a_n-1 = 2a_n-1 + a_n-2 implies a_n = frac12left(a_n-1 + a_n-2right).$$
answered Jul 25 at 4:20
B. Mehta
11.7k21944
edited Jul 26 at 17:11
answered Jul 25 at 4:20
B. Mehta
11.7k21944
answered Jul 25 at 4:20
B. Mehta
11.7k21944
answered Jul 25 at 4:20
B. Mehta
11.7k21944
11.7k21944
In the first paragraph, is not $c_1=1?$
– WalquerX
Jul 26 at 12:30
Yup, fixed. My mistake.
– B. Mehta
Jul 26 at 17:12
add a comment |Â
In the first paragraph, is not $c_1=1?$
– WalquerX
Jul 26 at 12:30
Yup, fixed. My mistake.
– B. Mehta
Jul 26 at 17:12
In the first paragraph, is not $c_1=1?$
– WalquerX
Jul 26 at 12:30
In the first paragraph, is not $c_1=1?$
– WalquerX
Jul 26 at 12:30
Yup, fixed. My mistake.
– B. Mehta
Jul 26 at 17:12
Yup, fixed. My mistake.
– B. Mehta
Jul 26 at 17:12
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%2f2862003%2fis-there-a-rule-behind-why-left-1-1-2n-right-infty-n-1-is%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
You are dealing with a homogenous recurrence, which can be solved using characteristic polynomials, have a look at this answer as an example ... apply the same technique, but be careful, you have difference initial conditions.
– rtybase
Jul 25 at 7:42