Mixing
Using a summation factor to solve a recurrence
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
On Princeton's Analysis of Algorithms, they discuss solving recurrence relations and they come across a line that I can't seem to decipher
beginalign
n(n-1)a_n &=(n-1)(n-2)a_n-1 + 2(n-1)\
&=(n-2)(n-3)a_n-2+2(n-2)+2(n-1)\
&=2(1+2+cdots+n-1)\
&=n(n-1)\
a_n&=1
endalign
Basically lines (1) through (4) I am not sure how they are making those simplifications. If it's a matter of reading up on some literature a reference would be greatly appreciated.
recurrence-relations
edited Jul 26 at 0:35
David K
48.1k340107
asked Jul 26 at 0:24
phandaman
676
add a comment |Â
up vote
0
down vote
favorite
On Princeton's Analysis of Algorithms, they discuss solving recurrence relations and they come across a line that I can't seem to decipher
beginalign
n(n-1)a_n &=(n-1)(n-2)a_n-1 + 2(n-1)\
&=(n-2)(n-3)a_n-2+2(n-2)+2(n-1)\
&=2(1+2+cdots+n-1)\
&=n(n-1)\
a_n&=1
endalign
Basically lines (1) through (4) I am not sure how they are making those simplifications. If it's a matter of reading up on some literature a reference would be greatly appreciated.
recurrence-relations
edited Jul 26 at 0:35
David K
48.1k340107
asked Jul 26 at 0:24
phandaman
676
It's easier to follow if you first define $,b_colorredn = colorredn(colorredn-1)a_colorredn-1,$. Then changing $,n mapsto n-1,$ gives $,b_colorredn-1 = colorred(n-1)(colorredn-1-1)a_colorredn-1-1$ $=(n-1)(n-2)a_n-2,$, so the recurrence can be written as $,b_n = b_n-1+2(n-1),$, then it telescopes from there on.
– dxiv
Jul 26 at 0:32
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
On Princeton's Analysis of Algorithms, they discuss solving recurrence relations and they come across a line that I can't seem to decipher
beginalign
n(n-1)a_n &=(n-1)(n-2)a_n-1 + 2(n-1)\
&=(n-2)(n-3)a_n-2+2(n-2)+2(n-1)\
&=2(1+2+cdots+n-1)\
&=n(n-1)\
a_n&=1
endalign
Basically lines (1) through (4) I am not sure how they are making those simplifications. If it's a matter of reading up on some literature a reference would be greatly appreciated.
recurrence-relations
edited Jul 26 at 0:35
David K
48.1k340107
asked Jul 26 at 0:24
phandaman
676
On Princeton's Analysis of Algorithms, they discuss solving recurrence relations and they come across a line that I can't seem to decipher
beginalign
n(n-1)a_n &=(n-1)(n-2)a_n-1 + 2(n-1)\
&=(n-2)(n-3)a_n-2+2(n-2)+2(n-1)\
&=2(1+2+cdots+n-1)\
&=n(n-1)\
a_n&=1
endalign
Basically lines (1) through (4) I am not sure how they are making those simplifications. If it's a matter of reading up on some literature a reference would be greatly appreciated.
recurrence-relations
edited Jul 26 at 0:35
David K
48.1k340107
asked Jul 26 at 0:24
phandaman
676
edited Jul 26 at 0:35
David K
48.1k340107
edited Jul 26 at 0:35
David K
48.1k340107
edited Jul 26 at 0:35
David K
48.1k340107
48.1k340107
asked Jul 26 at 0:24
phandaman
676
asked Jul 26 at 0:24
phandaman
676
asked Jul 26 at 0:24
phandaman
676
676
It's easier to follow if you first define $,b_colorredn = colorredn(colorredn-1)a_colorredn-1,$. Then changing $,n mapsto n-1,$ gives $,b_colorredn-1 = colorred(n-1)(colorredn-1-1)a_colorredn-1-1$ $=(n-1)(n-2)a_n-2,$, so the recurrence can be written as $,b_n = b_n-1+2(n-1),$, then it telescopes from there on.
– dxiv
Jul 26 at 0:32
add a comment |Â
It's easier to follow if you first define $,b_colorredn = colorredn(colorredn-1)a_colorredn-1,$. Then changing $,n mapsto n-1,$ gives $,b_colorredn-1 = colorred(n-1)(colorredn-1-1)a_colorredn-1-1$ $=(n-1)(n-2)a_n-2,$, so the recurrence can be written as $,b_n = b_n-1+2(n-1),$, then it telescopes from there on.
– dxiv
Jul 26 at 0:32
It's easier to follow if you first define $,b_colorredn = colorredn(colorredn-1)a_colorredn-1,$. Then changing $,n mapsto n-1,$ gives $,b_colorredn-1 = colorred(n-1)(colorredn-1-1)a_colorredn-1-1$ $=(n-1)(n-2)a_n-2,$, so the recurrence can be written as $,b_n = b_n-1+2(n-1),$, then it telescopes from there on.
– dxiv
Jul 26 at 0:32
It's easier to follow if you first define $,b_colorredn = colorredn(colorredn-1)a_colorredn-1,$. Then changing $,n mapsto n-1,$ gives $,b_colorredn-1 = colorred(n-1)(colorredn-1-1)a_colorredn-1-1$ $=(n-1)(n-2)a_n-2,$, so the recurrence can be written as $,b_n = b_n-1+2(n-1),$, then it telescopes from there on.
– dxiv
Jul 26 at 0:32
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
accepted
$$
n(n-1)a_n = (n-1)(n-2)a_n-1+2(n-1)
$$
Let $m = n-1$, then $(n-1)(n-2)a_n-1 = m(m-1)a_m$. From this, we can apply the recurrence again.
$$
n(n-1)a_n = [(m-1)(m-2)a_m-1+2(m-1)]+2(n-1)
$$
Then let $k = m-1$, then $(m-1)(m-2)a_m-1 = k(k-1)a_k$. We apply the recurrence again.
$$
n(n-1)a_n = left[[(k-1)(k-2)a_k-1+2(k-1)]+2(m-1)right]+2(n-1)
$$
And so on. Each time, we add another constant term on the right: first $2(n-1)$, then $2(m-1) = 2(n-2)$, then $2(k-1) = 2(n-3)$. This continues until we run out of positive terms.
answered Jul 26 at 0:30
Brian Tung
25.2k32353
add a comment |Â
up vote
1
down vote
The equality in line (2) just plugs in the definition of (1) back into the r.h.s. E.g. $(n-1)(n-2)a_n-1 = (n-2)(n-3)a_n-2+2(n-2)$.
The equality in line (3) comes from repeated use of (1). E.g:
$n(n-1)a_n = (n-k)(n-k+1)a_n-k + sum_i=1^k 2(n-i)$.
Can you take it from here?
If it helps, define $y_n:=n(n-1)a_n$. Then the recursion is rewritten to be $y_n=y_n-1+2(n-1)$. Then $y_n-y_n-1=2(n-1)$. Now sum both sides from $n=1$ to $n$. The left side will telescope.
Once you solve for $y_n$, you can then solve for $a_n$.
answered Jul 26 at 0:29
Alex R.
23.7k12352
I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_n-k$ dependence and give you a sum from $n=1$ to $n-1$?
– phandaman
Jul 26 at 2:28
@phandaman: see the second part with $y_n$.
– Alex R.
Jul 26 at 6:43
add a comment |Â
up vote
0
down vote
What this means is that if the first line is true for all $n$, then by induction you can prove that $n(n-1)a_n=n(n-1)$ and derive that $a_n=1$ for all $n$.
Implicitly the assumption $a_1=1$ must have been made somewhere above in the text.
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
$$
n(n-1)a_n = (n-1)(n-2)a_n-1+2(n-1)
$$
Let $m = n-1$, then $(n-1)(n-2)a_n-1 = m(m-1)a_m$. From this, we can apply the recurrence again.
$$
n(n-1)a_n = [(m-1)(m-2)a_m-1+2(m-1)]+2(n-1)
$$
Then let $k = m-1$, then $(m-1)(m-2)a_m-1 = k(k-1)a_k$. We apply the recurrence again.
$$
n(n-1)a_n = left[[(k-1)(k-2)a_k-1+2(k-1)]+2(m-1)right]+2(n-1)
$$
And so on. Each time, we add another constant term on the right: first $2(n-1)$, then $2(m-1) = 2(n-2)$, then $2(k-1) = 2(n-3)$. This continues until we run out of positive terms.
answered Jul 26 at 0:30
Brian Tung
25.2k32353
add a comment |Â
up vote
2
down vote
accepted
$$
n(n-1)a_n = (n-1)(n-2)a_n-1+2(n-1)
$$
Let $m = n-1$, then $(n-1)(n-2)a_n-1 = m(m-1)a_m$. From this, we can apply the recurrence again.
$$
n(n-1)a_n = [(m-1)(m-2)a_m-1+2(m-1)]+2(n-1)
$$
Then let $k = m-1$, then $(m-1)(m-2)a_m-1 = k(k-1)a_k$. We apply the recurrence again.
$$
n(n-1)a_n = left[[(k-1)(k-2)a_k-1+2(k-1)]+2(m-1)right]+2(n-1)
$$
And so on. Each time, we add another constant term on the right: first $2(n-1)$, then $2(m-1) = 2(n-2)$, then $2(k-1) = 2(n-3)$. This continues until we run out of positive terms.
answered Jul 26 at 0:30
Brian Tung
25.2k32353
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
$$
n(n-1)a_n = (n-1)(n-2)a_n-1+2(n-1)
$$
Let $m = n-1$, then $(n-1)(n-2)a_n-1 = m(m-1)a_m$. From this, we can apply the recurrence again.
$$
n(n-1)a_n = [(m-1)(m-2)a_m-1+2(m-1)]+2(n-1)
$$
Then let $k = m-1$, then $(m-1)(m-2)a_m-1 = k(k-1)a_k$. We apply the recurrence again.
$$
n(n-1)a_n = left[[(k-1)(k-2)a_k-1+2(k-1)]+2(m-1)right]+2(n-1)
$$
And so on. Each time, we add another constant term on the right: first $2(n-1)$, then $2(m-1) = 2(n-2)$, then $2(k-1) = 2(n-3)$. This continues until we run out of positive terms.
answered Jul 26 at 0:30
Brian Tung
25.2k32353
$$
n(n-1)a_n = (n-1)(n-2)a_n-1+2(n-1)
$$
Let $m = n-1$, then $(n-1)(n-2)a_n-1 = m(m-1)a_m$. From this, we can apply the recurrence again.
$$
n(n-1)a_n = [(m-1)(m-2)a_m-1+2(m-1)]+2(n-1)
$$
Then let $k = m-1$, then $(m-1)(m-2)a_m-1 = k(k-1)a_k$. We apply the recurrence again.
$$
n(n-1)a_n = left[[(k-1)(k-2)a_k-1+2(k-1)]+2(m-1)right]+2(n-1)
$$
And so on. Each time, we add another constant term on the right: first $2(n-1)$, then $2(m-1) = 2(n-2)$, then $2(k-1) = 2(n-3)$. This continues until we run out of positive terms.
answered Jul 26 at 0:30
Brian Tung
25.2k32353
answered Jul 26 at 0:30
Brian Tung
25.2k32353
answered Jul 26 at 0:30
Brian Tung
25.2k32353
answered Jul 26 at 0:30
Brian Tung
25.2k32353
25.2k32353
add a comment |Â
add a comment |Â
up vote
1
down vote
The equality in line (2) just plugs in the definition of (1) back into the r.h.s. E.g. $(n-1)(n-2)a_n-1 = (n-2)(n-3)a_n-2+2(n-2)$.
The equality in line (3) comes from repeated use of (1). E.g:
$n(n-1)a_n = (n-k)(n-k+1)a_n-k + sum_i=1^k 2(n-i)$.
Can you take it from here?
If it helps, define $y_n:=n(n-1)a_n$. Then the recursion is rewritten to be $y_n=y_n-1+2(n-1)$. Then $y_n-y_n-1=2(n-1)$. Now sum both sides from $n=1$ to $n$. The left side will telescope.
Once you solve for $y_n$, you can then solve for $a_n$.
answered Jul 26 at 0:29
Alex R.
23.7k12352
I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_n-k$ dependence and give you a sum from $n=1$ to $n-1$?
– phandaman
Jul 26 at 2:28
@phandaman: see the second part with $y_n$.
– Alex R.
Jul 26 at 6:43
add a comment |Â
up vote
1
down vote
The equality in line (2) just plugs in the definition of (1) back into the r.h.s. E.g. $(n-1)(n-2)a_n-1 = (n-2)(n-3)a_n-2+2(n-2)$.
The equality in line (3) comes from repeated use of (1). E.g:
$n(n-1)a_n = (n-k)(n-k+1)a_n-k + sum_i=1^k 2(n-i)$.
Can you take it from here?
If it helps, define $y_n:=n(n-1)a_n$. Then the recursion is rewritten to be $y_n=y_n-1+2(n-1)$. Then $y_n-y_n-1=2(n-1)$. Now sum both sides from $n=1$ to $n$. The left side will telescope.
Once you solve for $y_n$, you can then solve for $a_n$.
answered Jul 26 at 0:29
Alex R.
23.7k12352
I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_n-k$ dependence and give you a sum from $n=1$ to $n-1$?
– phandaman
Jul 26 at 2:28
@phandaman: see the second part with $y_n$.
– Alex R.
Jul 26 at 6:43
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The equality in line (2) just plugs in the definition of (1) back into the r.h.s. E.g. $(n-1)(n-2)a_n-1 = (n-2)(n-3)a_n-2+2(n-2)$.
The equality in line (3) comes from repeated use of (1). E.g:
$n(n-1)a_n = (n-k)(n-k+1)a_n-k + sum_i=1^k 2(n-i)$.
Can you take it from here?
If it helps, define $y_n:=n(n-1)a_n$. Then the recursion is rewritten to be $y_n=y_n-1+2(n-1)$. Then $y_n-y_n-1=2(n-1)$. Now sum both sides from $n=1$ to $n$. The left side will telescope.
Once you solve for $y_n$, you can then solve for $a_n$.
answered Jul 26 at 0:29
Alex R.
23.7k12352
The equality in line (2) just plugs in the definition of (1) back into the r.h.s. E.g. $(n-1)(n-2)a_n-1 = (n-2)(n-3)a_n-2+2(n-2)$.
The equality in line (3) comes from repeated use of (1). E.g:
$n(n-1)a_n = (n-k)(n-k+1)a_n-k + sum_i=1^k 2(n-i)$.
Can you take it from here?
If it helps, define $y_n:=n(n-1)a_n$. Then the recursion is rewritten to be $y_n=y_n-1+2(n-1)$. Then $y_n-y_n-1=2(n-1)$. Now sum both sides from $n=1$ to $n$. The left side will telescope.
Once you solve for $y_n$, you can then solve for $a_n$.
answered Jul 26 at 0:29
Alex R.
23.7k12352
answered Jul 26 at 0:29
Alex R.
23.7k12352
answered Jul 26 at 0:29
Alex R.
23.7k12352
answered Jul 26 at 0:29
Alex R.
23.7k12352
23.7k12352
I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_n-k$ dependence and give you a sum from $n=1$ to $n-1$?
– phandaman
Jul 26 at 2:28
@phandaman: see the second part with $y_n$.
– Alex R.
Jul 26 at 6:43
add a comment |Â
I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_n-k$ dependence and give you a sum from $n=1$ to $n-1$?
– phandaman
Jul 26 at 2:28
@phandaman: see the second part with $y_n$.
– Alex R.
Jul 26 at 6:43
I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_n-k$ dependence and give you a sum from $n=1$ to $n-1$?
– phandaman
Jul 26 at 2:28
I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_n-k$ dependence and give you a sum from $n=1$ to $n-1$?
– phandaman
Jul 26 at 2:28
@phandaman: see the second part with $y_n$.
– Alex R.
Jul 26 at 6:43
@phandaman: see the second part with $y_n$.
– Alex R.
Jul 26 at 6:43
add a comment |Â
up vote
0
down vote
What this means is that if the first line is true for all $n$, then by induction you can prove that $n(n-1)a_n=n(n-1)$ and derive that $a_n=1$ for all $n$.
Implicitly the assumption $a_1=1$ must have been made somewhere above in the text.
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
add a comment |Â
up vote
0
down vote
What this means is that if the first line is true for all $n$, then by induction you can prove that $n(n-1)a_n=n(n-1)$ and derive that $a_n=1$ for all $n$.
Implicitly the assumption $a_1=1$ must have been made somewhere above in the text.
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
add a comment |Â
up vote
0
down vote
up vote
0
down vote
What this means is that if the first line is true for all $n$, then by induction you can prove that $n(n-1)a_n=n(n-1)$ and derive that $a_n=1$ for all $n$.
Implicitly the assumption $a_1=1$ must have been made somewhere above in the text.
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
What this means is that if the first line is true for all $n$, then by induction you can prove that $n(n-1)a_n=n(n-1)$ and derive that $a_n=1$ for all $n$.
Implicitly the assumption $a_1=1$ must have been made somewhere above in the text.
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
answered Jul 26 at 0:31
Arnaud Mortier
18.7k22159
18.7k22159
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%2f2862960%2fusing-a-summation-factor-to-solve-a-recurrence%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
It's easier to follow if you first define $,b_colorredn = colorredn(colorredn-1)a_colorredn-1,$. Then changing $,n mapsto n-1,$ gives $,b_colorredn-1 = colorred(n-1)(colorredn-1-1)a_colorredn-1-1$ $=(n-1)(n-2)a_n-2,$, so the recurrence can be written as $,b_n = b_n-1+2(n-1),$, then it telescopes from there on.
– dxiv
Jul 26 at 0:32