Prove this recursion formula for Stirling numbers of the first kind: s n + 1 , k + 1 = ∑ i = k n ( i k ) s n , i

Question

Prove this recursion formula for Stirling numbers of the first kind:      s          n      +      1      ,      k      +      1        =      ∑          i      =      k              n                          (                    i      k                      )                  s          n      ,      i

jockedripperHZT · Accepted Answer

Using the formula for the falling factorial, note that  (  x      )          n      +      1        =  x  ⋅  (  x  −  1      )    n      .Develop the falling factorial in terms of Stirling numbers of the first kind and powers of   (  x  −  1      )    k  . Then, use Newton&#039;s binomial formula to expand the powers   (  x  −  1      )    k  . A bit of rearranging of the terms finishes the proof.From      ∑          i      =      0              n            ∑          k      =      0              i        s  (  n  ,  i  )                    (                    i      k                      )              (  −  1      )          i      −      k            x          k      +      1      you can rearrange as      ∑          k      =      0              n            ∑          i      =      k              n        s  (  n  ,  i  )                    (                    i      k                      )              (  −  1      )          i      −      k            x          k      +      1          .If you don&#039;t see this, work out some terms of this double sum explicitly, it should be obvious. Then the left hand side of the falling factorial equation is  (  x      )          n      +      1        =      ∑          k      =      0              n      +      1        s  (  n  +  1  ,  k  )      x    k    =      ∑          k      =      0              n        s  (  n  +  1  ,  k  +  1  )      x          k      +      1      Equating left and right hand side, we get  s  (  n  +  1  ,  k  +  1  )  =      ∑          i      =      k              n        s  (  n  ,  i  )                    (                    i      k                      )              (  −  1      )          i      −      k          .Now, this may seem different from the formula you were required to derive, but that&#039;s just because I derived a formula for the signed Stirling numbers of the first kind, whereas yours was probably for unsigned ones. No problem however, just multiply both sides of the equations by   (  −  1      )          k      −      n       and according to the definition on the wikipage, you will get the end result.

Prove this recursion formula for Stirling numbers of the first kind: S_(n+1, k+1)=Sum_(i=k)^n (i k) s_(n,i)

Answered question

Answer & Explanation

New Questions in Pre-Algebra