Show that ( n 1 ) 1 + ( n 2 ) 2 + ( n 3 ) 3 + ⋯ + ( n n ) n = ∑ r = 1 n 2 r − 1 r

Question

Show that                               (                            n        1                              )                      1    +                              (                            n        2                              )                      2    +                              (                            n        3                              )                      3    +  ⋯  +                              (                            n        n                              )                      n    =      ∑          r      =      1              n                          2        r            −      1        r

cestdugateauhcorr · Accepted Answer

You need the two identities:                                          (                                                n            −            1                    k                                      )                                +                                        (                                                n            −            1                                k            −            1                                                )                                =                                        (                                    n          k                                      )                              Let             S      n        =          ∑              r        =        1                    n                    1      r                                            (                                    n          r                                      )                               and note that (by def.)                                           (                                                n            −            1                    n                                      )                                =    0.                                ∑                      r            =            1                                n                                    1          r                                                                    (                                                    n              r                                                      )                                                                        =                  ∑                      r            =            1                                n                                    1          r                                                                    (                                                                    n                −                1                            r                                                      )                                                    +                  ∑                      r            =            1                                n                                    1          r                                                                    (                                                                    n                −                1                                            r                −                1                                                                    )                                                                                      =                  ∑                      r            =            1                                n            −            1                                    1          r                                                                    (                                                                    n                −                1                            r                                                      )                                                    +                  ∑                      r            =            1                                n                                    r                      r            ⋅            n                                                                              (                                                    n              r                                                      )                                                                                      =                  ∑                      r            =            1                                n            −            1                                    1          r                                                                    (                                                                    n                −                1                            r                                                      )                                                    +                  1          n                          ∑                      r            =            1                                n                                                                              (                                                    n              r                                                      )                                                                                      =                  ∑                      r            =            1                                n            −            1                                    1          r                                                                    (                                                                    n                −                1                            r                                                      )                                                    +                                            2              n                        −            1                    n                                                  =                                            2              n                        −            1                    n                +                  S                      n            −            1                              Working with this recurrent relation, with       S    0    =  0 we have:                              S          n                                    =                                            2              n                        −            1                    n                +                  S                      n            −            1                                                            =                                            2                              n                                      −            1                    n                +                                            2                              n                −                1                                      −            1                                n            −            1                          +                  S                      n            −            2                                                            =                                            2                              n                                      −            1                    n                +                                            2                              n                −                1                                      −            1                                n            −            1                          +        ⋯        +                                            2                              1                                      −            1                    1                +                  S          0                                                  =                  ∑                      r            =            1                                n                                                              2              r                        −            1                    r

Rachel Ross · Accepted Answer

Alternatively: you&#039;ve shown that            ∫              0                    1                                      (          1          +          x                      )                          n                                −          1                x              d    x    =          ∑              r        =        1                    n                                      2          r                −        1            r      Since       (    1    +    x          )      n        −    1    =          ∑              r        =        1                    n                    x      r                                (                            n        r                              )                     we can write:                              ∑                      r            =            1                                n                                                              2              r                        −            1                    r                                    =                  ∫                      0                                1                                                              (              1              +              x                              )                                  n                                            −              1                        x                                            d                x                                          =                  ∫                      0                                1                                    1          x                          ∑                      r            =            1                                n                                    x          r                                                    (                                            n            r                                              )                                                        d                x                                          =                  ∫                      0                                1                                    ∑                      r            =            1                                n                                    x                      r            −            1                                                              (                                            n            r                                              )                                                        d                x                                          =                  ∑                      r            =            1                                n                                    ∫                      0                                1                                    x                      r            −            1                                                              (                                            n            r                                              )                                                        d                x                                          =                  ∑                      r            =            1                                n                                    1          r                                                    (                                            n            r                                              )                                      .

Show that <mstyle scriptlevel="0"> <mrow class="MJX-TeXAtom-OPEN">

Answered question

Answer & Explanation

New Questions in Precalculus