Mixing
Evaluating $sum_i=0^k-1 4^i(i-1)$ for recurrence relation exercise [duplicate]
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
This question already has an answer here:
Formula for calculating $sum_n=0^mnr^n$
4 answers
I need help to solve the following sum:
$$sum_i=0^k-1 4^i(i-1)$$
I'm doing some exercises about recurrence relations in algorithms and this sum came up.
The exercise stands like:
$$T(n) = frac 12n + 4T(fracn2 + 3)$$
And the result I get was:
$$ T(n) = 4^n T(fracn2^k+3k)+[sum_i=0^k-1frac4^in2^i+1+4^i*3*(i-1)]$$
All of this is new to me, all the examples i saw online are way more different than this excercise
Am I getting closer to an answer?
Note: No base case was given
Thanks in advance!
algorithms recurrence-relations
asked Jul 29 at 21:37
Diego Sepúlveda
83
marked as duplicate by Hans Lundmark, Lord Shark the Unknown, Arnaud D., amWhy, Shailesh Aug 2 at 11:57
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
1
down vote
favorite
This question already has an answer here:
Formula for calculating $sum_n=0^mnr^n$
4 answers
I need help to solve the following sum:
$$sum_i=0^k-1 4^i(i-1)$$
I'm doing some exercises about recurrence relations in algorithms and this sum came up.
The exercise stands like:
$$T(n) = frac 12n + 4T(fracn2 + 3)$$
And the result I get was:
$$ T(n) = 4^n T(fracn2^k+3k)+[sum_i=0^k-1frac4^in2^i+1+4^i*3*(i-1)]$$
All of this is new to me, all the examples i saw online are way more different than this excercise
Am I getting closer to an answer?
Note: No base case was given
Thanks in advance!
algorithms recurrence-relations
asked Jul 29 at 21:37
Diego Sepúlveda
83
marked as duplicate by Hans Lundmark, Lord Shark the Unknown, Arnaud D., amWhy, Shailesh Aug 2 at 11:57
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This question already has an answer here:
Formula for calculating $sum_n=0^mnr^n$
4 answers
I need help to solve the following sum:
$$sum_i=0^k-1 4^i(i-1)$$
I'm doing some exercises about recurrence relations in algorithms and this sum came up.
The exercise stands like:
$$T(n) = frac 12n + 4T(fracn2 + 3)$$
And the result I get was:
$$ T(n) = 4^n T(fracn2^k+3k)+[sum_i=0^k-1frac4^in2^i+1+4^i*3*(i-1)]$$
All of this is new to me, all the examples i saw online are way more different than this excercise
Am I getting closer to an answer?
Note: No base case was given
Thanks in advance!
algorithms recurrence-relations
asked Jul 29 at 21:37
Diego Sepúlveda
83
This question already has an answer here:
Formula for calculating $sum_n=0^mnr^n$
4 answers
I need help to solve the following sum:
$$sum_i=0^k-1 4^i(i-1)$$
I'm doing some exercises about recurrence relations in algorithms and this sum came up.
The exercise stands like:
$$T(n) = frac 12n + 4T(fracn2 + 3)$$
And the result I get was:
$$ T(n) = 4^n T(fracn2^k+3k)+[sum_i=0^k-1frac4^in2^i+1+4^i*3*(i-1)]$$
All of this is new to me, all the examples i saw online are way more different than this excercise
Am I getting closer to an answer?
Note: No base case was given
Thanks in advance!
This question already has an answer here:
Formula for calculating $sum_n=0^mnr^n$
4 answers
algorithms recurrence-relations
asked Jul 29 at 21:37
Diego Sepúlveda
83
edited Jul 29 at 21:51
asked Jul 29 at 21:37
Diego Sepúlveda
83
asked Jul 29 at 21:37
Diego Sepúlveda
83
asked Jul 29 at 21:37
Diego Sepúlveda
83
83
marked as duplicate by Hans Lundmark, Lord Shark the Unknown, Arnaud D., amWhy, Shailesh Aug 2 at 11:57
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Hans Lundmark, Lord Shark the Unknown, Arnaud D., amWhy, Shailesh Aug 2 at 11:57
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
One way might be$$A=sum _ i=0 ^ k-1 4^ i (i-1)=-1+ 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ A+1= 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ 4left( A+1 right) = 4 ^ 3 + 4 ^ 4 cdot 2+ 4 ^ 5 cdot 3+...+ 4 ^ k left( k-2 right) \ left( A+1 right) -4left( A+1 right) = 4 ^ 2 +left( 4 ^ 3 cdot 2- 4 ^ 3 right) +left( 4 ^ 4 cdot 3- 4 ^ 4 cdot 2 right) +...+left( 4 ^ k-1 left( k-2 right) - 4 ^ k-1 left( k-3 right) right) - 4 ^ k left( k-2 right) \ -3left( A+1 right) = 4 ^ 2 + 4 ^ 3 +...+ 4 ^ k-1 - 4 ^ k left( k-2 right) \ -3left( A+1 right) =frac 4 ^ 2 left( 1- 4 ^ k right) 1-4 - 4 ^ k left( k-2 right) = 4 ^ k left( frac 22 3 -k right) \ A=frac 4 ^ k -3 left( frac 22 3 -k right) -1\ $$
or finding a derivative of $sum _ i=0 ^ n x ^ n $
answered Jul 29 at 21:53
haqnatural
20.5k72457
This is amazing, thanks!
– Diego Sepúlveda
Jul 29 at 21:55
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
One way might be$$A=sum _ i=0 ^ k-1 4^ i (i-1)=-1+ 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ A+1= 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ 4left( A+1 right) = 4 ^ 3 + 4 ^ 4 cdot 2+ 4 ^ 5 cdot 3+...+ 4 ^ k left( k-2 right) \ left( A+1 right) -4left( A+1 right) = 4 ^ 2 +left( 4 ^ 3 cdot 2- 4 ^ 3 right) +left( 4 ^ 4 cdot 3- 4 ^ 4 cdot 2 right) +...+left( 4 ^ k-1 left( k-2 right) - 4 ^ k-1 left( k-3 right) right) - 4 ^ k left( k-2 right) \ -3left( A+1 right) = 4 ^ 2 + 4 ^ 3 +...+ 4 ^ k-1 - 4 ^ k left( k-2 right) \ -3left( A+1 right) =frac 4 ^ 2 left( 1- 4 ^ k right) 1-4 - 4 ^ k left( k-2 right) = 4 ^ k left( frac 22 3 -k right) \ A=frac 4 ^ k -3 left( frac 22 3 -k right) -1\ $$
or finding a derivative of $sum _ i=0 ^ n x ^ n $
answered Jul 29 at 21:53
haqnatural
20.5k72457
This is amazing, thanks!
– Diego Sepúlveda
Jul 29 at 21:55
add a comment |Â
up vote
0
down vote
accepted
One way might be$$A=sum _ i=0 ^ k-1 4^ i (i-1)=-1+ 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ A+1= 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ 4left( A+1 right) = 4 ^ 3 + 4 ^ 4 cdot 2+ 4 ^ 5 cdot 3+...+ 4 ^ k left( k-2 right) \ left( A+1 right) -4left( A+1 right) = 4 ^ 2 +left( 4 ^ 3 cdot 2- 4 ^ 3 right) +left( 4 ^ 4 cdot 3- 4 ^ 4 cdot 2 right) +...+left( 4 ^ k-1 left( k-2 right) - 4 ^ k-1 left( k-3 right) right) - 4 ^ k left( k-2 right) \ -3left( A+1 right) = 4 ^ 2 + 4 ^ 3 +...+ 4 ^ k-1 - 4 ^ k left( k-2 right) \ -3left( A+1 right) =frac 4 ^ 2 left( 1- 4 ^ k right) 1-4 - 4 ^ k left( k-2 right) = 4 ^ k left( frac 22 3 -k right) \ A=frac 4 ^ k -3 left( frac 22 3 -k right) -1\ $$
or finding a derivative of $sum _ i=0 ^ n x ^ n $
answered Jul 29 at 21:53
haqnatural
20.5k72457
This is amazing, thanks!
– Diego Sepúlveda
Jul 29 at 21:55
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
One way might be$$A=sum _ i=0 ^ k-1 4^ i (i-1)=-1+ 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ A+1= 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ 4left( A+1 right) = 4 ^ 3 + 4 ^ 4 cdot 2+ 4 ^ 5 cdot 3+...+ 4 ^ k left( k-2 right) \ left( A+1 right) -4left( A+1 right) = 4 ^ 2 +left( 4 ^ 3 cdot 2- 4 ^ 3 right) +left( 4 ^ 4 cdot 3- 4 ^ 4 cdot 2 right) +...+left( 4 ^ k-1 left( k-2 right) - 4 ^ k-1 left( k-3 right) right) - 4 ^ k left( k-2 right) \ -3left( A+1 right) = 4 ^ 2 + 4 ^ 3 +...+ 4 ^ k-1 - 4 ^ k left( k-2 right) \ -3left( A+1 right) =frac 4 ^ 2 left( 1- 4 ^ k right) 1-4 - 4 ^ k left( k-2 right) = 4 ^ k left( frac 22 3 -k right) \ A=frac 4 ^ k -3 left( frac 22 3 -k right) -1\ $$
or finding a derivative of $sum _ i=0 ^ n x ^ n $
answered Jul 29 at 21:53
haqnatural
20.5k72457
One way might be$$A=sum _ i=0 ^ k-1 4^ i (i-1)=-1+ 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ A+1= 4 ^ 2 + 4 ^ 3 cdot 2+ 4 ^ 4 cdot 3+...+ 4 ^ k-1 left( k-2 right) \ 4left( A+1 right) = 4 ^ 3 + 4 ^ 4 cdot 2+ 4 ^ 5 cdot 3+...+ 4 ^ k left( k-2 right) \ left( A+1 right) -4left( A+1 right) = 4 ^ 2 +left( 4 ^ 3 cdot 2- 4 ^ 3 right) +left( 4 ^ 4 cdot 3- 4 ^ 4 cdot 2 right) +...+left( 4 ^ k-1 left( k-2 right) - 4 ^ k-1 left( k-3 right) right) - 4 ^ k left( k-2 right) \ -3left( A+1 right) = 4 ^ 2 + 4 ^ 3 +...+ 4 ^ k-1 - 4 ^ k left( k-2 right) \ -3left( A+1 right) =frac 4 ^ 2 left( 1- 4 ^ k right) 1-4 - 4 ^ k left( k-2 right) = 4 ^ k left( frac 22 3 -k right) \ A=frac 4 ^ k -3 left( frac 22 3 -k right) -1\ $$
or finding a derivative of $sum _ i=0 ^ n x ^ n $
answered Jul 29 at 21:53
haqnatural
20.5k72457
edited Jul 29 at 21:59
answered Jul 29 at 21:53
haqnatural
20.5k72457
answered Jul 29 at 21:53
haqnatural
20.5k72457
answered Jul 29 at 21:53
haqnatural
20.5k72457
20.5k72457
This is amazing, thanks!
– Diego Sepúlveda
Jul 29 at 21:55
add a comment |Â
This is amazing, thanks!
– Diego Sepúlveda
Jul 29 at 21:55
This is amazing, thanks!
– Diego Sepúlveda
Jul 29 at 21:55
This is amazing, thanks!
– Diego Sepúlveda
Jul 29 at 21:55
add a comment |Â