Evaluating $sum_i=0^k-1 4^i(i-1)$ for recurrence relation exercise [duplicate]

The name of the pictureThe name of the pictureThe name of the pictureClash 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!







share|cite|improve this 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.


















    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!







    share|cite|improve this 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.
















      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!







      share|cite|improve this question














      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









      share|cite|improve this question












      share|cite|improve this question




      share|cite|improve this question








      edited Jul 29 at 21:51
























      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.






















          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 $






          share|cite|improve this answer























          • This is amazing, thanks!
            – Diego Sepúlveda
            Jul 29 at 21:55

















          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 $






          share|cite|improve this answer























          • This is amazing, thanks!
            – Diego Sepúlveda
            Jul 29 at 21:55














          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 $






          share|cite|improve this answer























          • This is amazing, thanks!
            – Diego Sepúlveda
            Jul 29 at 21:55












          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 $






          share|cite|improve this answer















          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 $







          share|cite|improve this answer















          share|cite|improve this answer



          share|cite|improve this answer








          edited Jul 29 at 21:59


























          answered Jul 29 at 21:53









          haqnatural

          20.5k72457




          20.5k72457











          • 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




          This is amazing, thanks!
          – Diego Sepúlveda
          Jul 29 at 21:55


          Comments

          Popular posts from this blog

          What is the equation of a 3D cone with generalised tilt?

          Relationship between determinant of matrix and determinant of adjoint?

          Color the edges and diagonals of a regular polygon