Sum of floor function












0












$begingroup$


I have the following question:



Show that $displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k)$



then evaluate $displaystylesum_{k=1}^n lfloor log_2(k) rfloor=(n+1)lfloor log_2(n) rfloor -2^{lfloor log_2(n) rfloor+1}+2$



I can show the first part pretty easily by induction but I have no idea where to go with the second part. I use the expansion and get:



$displaystylesum_{k=1}^n lfloor log_2(k) rfloor=nlfloor log_2(n) rfloor-displaystylesum_{k=1}^{n-1} k(lfloor log_2(k+1) rfloor-lfloor log_2(k) rfloor)$ but I have no idea where to go from here.



Thanks for any help.






sequences-and-series







share|cite|improve this question











$endgroup$

















    0












    $begingroup$


    I have the following question:



    Show that $displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k)$



    then evaluate $displaystylesum_{k=1}^n lfloor log_2(k) rfloor=(n+1)lfloor log_2(n) rfloor -2^{lfloor log_2(n) rfloor+1}+2$



    I can show the first part pretty easily by induction but I have no idea where to go with the second part. I use the expansion and get:



    $displaystylesum_{k=1}^n lfloor log_2(k) rfloor=nlfloor log_2(n) rfloor-displaystylesum_{k=1}^{n-1} k(lfloor log_2(k+1) rfloor-lfloor log_2(k) rfloor)$ but I have no idea where to go from here.



    Thanks for any help.






    sequences-and-series







    share|cite|improve this question











    $endgroup$















      0












      0








      0





      $begingroup$


      I have the following question:



      Show that $displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k)$



      then evaluate $displaystylesum_{k=1}^n lfloor log_2(k) rfloor=(n+1)lfloor log_2(n) rfloor -2^{lfloor log_2(n) rfloor+1}+2$



      I can show the first part pretty easily by induction but I have no idea where to go with the second part. I use the expansion and get:



      $displaystylesum_{k=1}^n lfloor log_2(k) rfloor=nlfloor log_2(n) rfloor-displaystylesum_{k=1}^{n-1} k(lfloor log_2(k+1) rfloor-lfloor log_2(k) rfloor)$ but I have no idea where to go from here.



      Thanks for any help.






      sequences-and-series







      share|cite|improve this question











      $endgroup$




      I have the following question:



      Show that $displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k)$



      then evaluate $displaystylesum_{k=1}^n lfloor log_2(k) rfloor=(n+1)lfloor log_2(n) rfloor -2^{lfloor log_2(n) rfloor+1}+2$



      I can show the first part pretty easily by induction but I have no idea where to go with the second part. I use the expansion and get:



      $displaystylesum_{k=1}^n lfloor log_2(k) rfloor=nlfloor log_2(n) rfloor-displaystylesum_{k=1}^{n-1} k(lfloor log_2(k+1) rfloor-lfloor log_2(k) rfloor)$ but I have no idea where to go from here.



      Thanks for any help.






      sequences-and-series




      sequences-and-series






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 11 at 15:14







      hmmmm

















      asked Sep 28 '12 at 12:19









      hmmmmhmmmm

      2,65422760




      2,65422760






















          3 Answers
          3






          active

          oldest

          votes


















          3












          $begingroup$

          You (now) have



          $$sum_{k=1}^nlfloorlg nrfloor=nlfloorlg krfloor-sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig);,$$



          where I use $lg$ for $log_2$. Now notice that when $2^mle k<k+1<2^{m+1}$, $lg k=lg(k+1)$, and the corresponding term in the last summation is $0$. You get a non-zero term only when $k=2^m-1$ for some $m$, and in that case the term that you get is $k$. Thus,



          $$sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig)=sum_{1le mlelg n}left(2^m-1right)=sum_{m=1}^{lfloorlg nrfloor}left(2^m-1right);.$$



          From here you should be able to finish it; it’s just a little algebra now.






          share|cite|improve this answer









          $endgroup$





















            1












            $begingroup$

            If you explicitly write out the first several terms in your second summation $sum_{k=1}^{n-1}k(lfloor log_2(k+1)rfloor - lfloor log_2(k)rfloor)$, you will find out all terms are zero except when $k=2^s-1$ where $s$ is an integer less than $lfloor log_2(n)rfloor$. Then it becomes a geometrical series and it's easy to sum it up and get a nice result.






            share|cite|improve this answer









            $endgroup$





















              0












              $begingroup$

              You are asked to show first



              $$ displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k) ,.$$



              To prove this you need to use summation by parts



              $$ sum_{k=m}^n f_k(g_{k+1}-g_k) = left[f_{n+1}g_{n+1} - f_m g_mright] - sum_{k=m}^n g_{k+1}(f_{k+1}- f_k),. $$



              In your case, let $f_k=a_k$ and $g_k=k Rightarrow g_{k+1}-g_k=1$.






              share|cite|improve this answer











              $endgroup$













              • $begingroup$
                I'm pretty sure that I can just use induction to show this?
                $endgroup$
                – hmmmm
                Sep 29 '12 at 15:02











              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "69"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              autoActivateHeartbeat: false,
              convertImagesToLinks: true,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: 10,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              noCode: true, onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });














              draft saved

              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f203948%2fsum-of-floor-function%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              3 Answers
              3






              active

              oldest

              votes








              3 Answers
              3






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              3












              $begingroup$

              You (now) have



              $$sum_{k=1}^nlfloorlg nrfloor=nlfloorlg krfloor-sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig);,$$



              where I use $lg$ for $log_2$. Now notice that when $2^mle k<k+1<2^{m+1}$, $lg k=lg(k+1)$, and the corresponding term in the last summation is $0$. You get a non-zero term only when $k=2^m-1$ for some $m$, and in that case the term that you get is $k$. Thus,



              $$sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig)=sum_{1le mlelg n}left(2^m-1right)=sum_{m=1}^{lfloorlg nrfloor}left(2^m-1right);.$$



              From here you should be able to finish it; it’s just a little algebra now.






              share|cite|improve this answer









              $endgroup$


















                3












                $begingroup$

                You (now) have



                $$sum_{k=1}^nlfloorlg nrfloor=nlfloorlg krfloor-sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig);,$$



                where I use $lg$ for $log_2$. Now notice that when $2^mle k<k+1<2^{m+1}$, $lg k=lg(k+1)$, and the corresponding term in the last summation is $0$. You get a non-zero term only when $k=2^m-1$ for some $m$, and in that case the term that you get is $k$. Thus,



                $$sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig)=sum_{1le mlelg n}left(2^m-1right)=sum_{m=1}^{lfloorlg nrfloor}left(2^m-1right);.$$



                From here you should be able to finish it; it’s just a little algebra now.






                share|cite|improve this answer









                $endgroup$
















                  3












                  3








                  3





                  $begingroup$

                  You (now) have



                  $$sum_{k=1}^nlfloorlg nrfloor=nlfloorlg krfloor-sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig);,$$



                  where I use $lg$ for $log_2$. Now notice that when $2^mle k<k+1<2^{m+1}$, $lg k=lg(k+1)$, and the corresponding term in the last summation is $0$. You get a non-zero term only when $k=2^m-1$ for some $m$, and in that case the term that you get is $k$. Thus,



                  $$sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig)=sum_{1le mlelg n}left(2^m-1right)=sum_{m=1}^{lfloorlg nrfloor}left(2^m-1right);.$$



                  From here you should be able to finish it; it’s just a little algebra now.






                  share|cite|improve this answer









                  $endgroup$



                  You (now) have



                  $$sum_{k=1}^nlfloorlg nrfloor=nlfloorlg krfloor-sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig);,$$



                  where I use $lg$ for $log_2$. Now notice that when $2^mle k<k+1<2^{m+1}$, $lg k=lg(k+1)$, and the corresponding term in the last summation is $0$. You get a non-zero term only when $k=2^m-1$ for some $m$, and in that case the term that you get is $k$. Thus,



                  $$sum_{k=1}^{n-1}kBig(lfloorlg(k+1)rfloor-lfloorlg krfloorBig)=sum_{1le mlelg n}left(2^m-1right)=sum_{m=1}^{lfloorlg nrfloor}left(2^m-1right);.$$



                  From here you should be able to finish it; it’s just a little algebra now.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Sep 28 '12 at 12:37









                  Brian M. ScottBrian M. Scott

                  457k38510909




                  457k38510909























                      1












                      $begingroup$

                      If you explicitly write out the first several terms in your second summation $sum_{k=1}^{n-1}k(lfloor log_2(k+1)rfloor - lfloor log_2(k)rfloor)$, you will find out all terms are zero except when $k=2^s-1$ where $s$ is an integer less than $lfloor log_2(n)rfloor$. Then it becomes a geometrical series and it's easy to sum it up and get a nice result.






                      share|cite|improve this answer









                      $endgroup$


















                        1












                        $begingroup$

                        If you explicitly write out the first several terms in your second summation $sum_{k=1}^{n-1}k(lfloor log_2(k+1)rfloor - lfloor log_2(k)rfloor)$, you will find out all terms are zero except when $k=2^s-1$ where $s$ is an integer less than $lfloor log_2(n)rfloor$. Then it becomes a geometrical series and it's easy to sum it up and get a nice result.






                        share|cite|improve this answer









                        $endgroup$
















                          1












                          1








                          1





                          $begingroup$

                          If you explicitly write out the first several terms in your second summation $sum_{k=1}^{n-1}k(lfloor log_2(k+1)rfloor - lfloor log_2(k)rfloor)$, you will find out all terms are zero except when $k=2^s-1$ where $s$ is an integer less than $lfloor log_2(n)rfloor$. Then it becomes a geometrical series and it's easy to sum it up and get a nice result.






                          share|cite|improve this answer









                          $endgroup$



                          If you explicitly write out the first several terms in your second summation $sum_{k=1}^{n-1}k(lfloor log_2(k+1)rfloor - lfloor log_2(k)rfloor)$, you will find out all terms are zero except when $k=2^s-1$ where $s$ is an integer less than $lfloor log_2(n)rfloor$. Then it becomes a geometrical series and it's easy to sum it up and get a nice result.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered Sep 28 '12 at 12:38









                          Patrick LiPatrick Li

                          2,99941633




                          2,99941633























                              0












                              $begingroup$

                              You are asked to show first



                              $$ displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k) ,.$$



                              To prove this you need to use summation by parts



                              $$ sum_{k=m}^n f_k(g_{k+1}-g_k) = left[f_{n+1}g_{n+1} - f_m g_mright] - sum_{k=m}^n g_{k+1}(f_{k+1}- f_k),. $$



                              In your case, let $f_k=a_k$ and $g_k=k Rightarrow g_{k+1}-g_k=1$.






                              share|cite|improve this answer











                              $endgroup$













                              • $begingroup$
                                I'm pretty sure that I can just use induction to show this?
                                $endgroup$
                                – hmmmm
                                Sep 29 '12 at 15:02
















                              0












                              $begingroup$

                              You are asked to show first



                              $$ displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k) ,.$$



                              To prove this you need to use summation by parts



                              $$ sum_{k=m}^n f_k(g_{k+1}-g_k) = left[f_{n+1}g_{n+1} - f_m g_mright] - sum_{k=m}^n g_{k+1}(f_{k+1}- f_k),. $$



                              In your case, let $f_k=a_k$ and $g_k=k Rightarrow g_{k+1}-g_k=1$.






                              share|cite|improve this answer











                              $endgroup$













                              • $begingroup$
                                I'm pretty sure that I can just use induction to show this?
                                $endgroup$
                                – hmmmm
                                Sep 29 '12 at 15:02














                              0












                              0








                              0





                              $begingroup$

                              You are asked to show first



                              $$ displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k) ,.$$



                              To prove this you need to use summation by parts



                              $$ sum_{k=m}^n f_k(g_{k+1}-g_k) = left[f_{n+1}g_{n+1} - f_m g_mright] - sum_{k=m}^n g_{k+1}(f_{k+1}- f_k),. $$



                              In your case, let $f_k=a_k$ and $g_k=k Rightarrow g_{k+1}-g_k=1$.






                              share|cite|improve this answer











                              $endgroup$



                              You are asked to show first



                              $$ displaystylesum_{k=1}^n a_k=na_n-displaystylesum_{k=1}^{n-1} k(a_{k+1}-a_k) ,.$$



                              To prove this you need to use summation by parts



                              $$ sum_{k=m}^n f_k(g_{k+1}-g_k) = left[f_{n+1}g_{n+1} - f_m g_mright] - sum_{k=m}^n g_{k+1}(f_{k+1}- f_k),. $$



                              In your case, let $f_k=a_k$ and $g_k=k Rightarrow g_{k+1}-g_k=1$.







                              share|cite|improve this answer














                              share|cite|improve this answer



                              share|cite|improve this answer








                              edited Sep 28 '12 at 13:18

























                              answered Sep 28 '12 at 12:56









                              Mhenni BenghorbalMhenni Benghorbal

                              43.1k63574




                              43.1k63574












                              • $begingroup$
                                I'm pretty sure that I can just use induction to show this?
                                $endgroup$
                                – hmmmm
                                Sep 29 '12 at 15:02


















                              • $begingroup$
                                I'm pretty sure that I can just use induction to show this?
                                $endgroup$
                                – hmmmm
                                Sep 29 '12 at 15:02
















                              $begingroup$
                              I'm pretty sure that I can just use induction to show this?
                              $endgroup$
                              – hmmmm
                              Sep 29 '12 at 15:02




                              $begingroup$
                              I'm pretty sure that I can just use induction to show this?
                              $endgroup$
                              – hmmmm
                              Sep 29 '12 at 15:02


















                              draft saved

                              draft discarded




















































                              Thanks for contributing an answer to Mathematics Stack Exchange!


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid …



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              Use MathJax to format equations. MathJax reference.


                              To learn more, see our tips on writing great answers.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f203948%2fsum-of-floor-function%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              Popular posts from this blog

                              MongoDB - Not Authorized To Execute Command

                              Image
                              .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
                              Read more

                              How to fix TextFormField cause rebuild widget in Flutter

                              Image
                              .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I've got the same issue at #9280. I tried all solutions from that topic with/without GlobalKey for Scaffold and Form but the problem wasn't fixed. I tried to build a authentication form with login and signup. But the keyboard doesn't show when I tap the TextFormField at the first time. Then I try to input some letter from physical keyboard, the widget is rebuilt. Like this: login screen Nothing to be log when I run flutter run --verbose, so I logged manually. Every tapping on field, the widget called dispose -> init -> build. [√] Flutter (Channel beta, v1.0.0, on Microsoft Windows [Version 10.0.17763.195], ...
                              Read more

                              Npm cannot find a required file even through it is in the searched directory

                              Image
                              up vote 0 down vote favorite I got that error: users-Air:pdfuploader user$ npm run start client@0.1.0 start /Users/user/Documents/pdfuploader react-scripts start Could not find a required file. Name: index.html Searched in: /Users/user/Documents/pdfuploader/public npm ERR! code ELIFECYCLE npm ERR! errno 1 npm ERR! client@0.1.0 start: `react-scripts start` npm ERR! Exit status 1 npm ERR! npm ERR! Failed at the client@0.1.0 start script. npm ERR! This is probably not a problem with npm. There is likely additional logging output above. npm ERR! A complete log of this run can be found in: npm ERR! /Users/user/.npm/_logs/2018-11-19T10_19_14_555Z-debug.log users-Air:pdfuploader user$ And the file is in /Users/user/Documents/pdfuploader/public as you can see in my github repository: https://github.c...
                              Read more