Prove that ∑ k = 0 m ( m k ) ( n k ) = n + 1 n + 1 − m

Question

Prove that       ∑          k      =      0              m                                    (                            m        k                              )                                              (                            n        k                              )                      =            n      +      1              n      +      1      −      m

Kason Gonzales · Accepted Answer

Step 1You can solve your problem by following these steps:1) First show that                                          (                                    m          k                                      )                                                            (                                    n          k                                      )                                =                                          (                                                n            −            k                                m            −            k                                                )                                                            (                                    n          m                                      )                                .2) Now show that                    (                    n      m                      )              ⋅                    n        +        1                    n        +        1        −        m              =                    (                            n        +        1            m                      )              .3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving      ∑          k      =      0        m                      (                            n        −        k                    m        −        k                            )              =                    (                            n        +        1            m                      )              .4) Now prove the relation:      ∑          k      =      0        m                      (                            n        −        k                    m        −        k                            )              =                    (                            n        +        1            m                      )              .Step 24a) You can prove this relation in various ways. One of them is to write                     (                            n        −        m            0                      )             as                     (                            n        −        m        +        1            0                      )             and then repeatedly use the relation                     (                    x      r                      )              +                    (                    x              r        −        1                            )              =                    (                            x        +        1            r                      )            . Another method is induction.

mafalexpicsak · Accepted Answer

Step 1                                          ∑                          k              =              0                                      m                                                                                                                                      (                                                                            m                    k                                                                              )                                                                                                                                                              (                                                                            n                    k                                                                              )                                                                                                    =                                                    n                +                1                                            n                +                1                −                m                                                        :                               ?                    Step 2                                                              ∑                              k                =                0                                            m                                                                                                                                                        (                                                                                    m                      k                                                                                      )                                                                                                                                                                                (                                                                                    n                      k                                                                                      )                                                                                                                                =                  (                                n            +            1                              )                          ∑                      k            =            0                                m                                                                              (                                                    m              k                                                      )                                                                                                Γ                              (                                                  k                  +                  1                                                )                            Γ                              (                                                  n                  −                  k                  +                  1                                                )                                                    Γ                              (                                                  n                  +                  2                                                )                                                                        =                                       (                                n            +            1                              )                          ∑                      k            =            0                                m                                                                              (                                                    m              k                                                      )                                                              ∫                      0                                1                                    t                      k                                                (                                      1              −              t                                    )                                n            −            k                                            d                t                            =                                       (                                n            +            1                              )                          ∫                      0                                1                                                (                                      1              −              t                                    )                                n                                    ∑                      k            =            0                                m                                                                              (                                                    m              k                                                      )                                                                          (                                                      t                                  1                  −                  t                                                                  )                                k                                            d                t                            =                                       (                                n            +            1                              )                          ∫                      0                                1                                                (                                      1              −              t                                    )                                n                                                (                                      1              +                                                t                                      1                    −                    t                                                                                    )                                m                                            d                t                            =                                       (                                n            +            1                              )                          ∫                      0                                1                                                (                                      1              −              t                                    )                                n            −            m                                            d                t        =                                                                                                          n                    +                    1                                                        n                    +                    1                    −                    m

Prove that sum_{k=0}^{m} (((m),(k)))/(((a),(b)))=(n+1)/(n+1-m)

Answered question

Answer & Explanation

New Questions in High school probability