Algorithm to find Sum of the first r binomial coefficients for fixed n modulo m

Question

I am trying to find the sum of the first r binomial coefficients for a fixed n.

(nC1 + nC2 + nC3 + ... + nCr) % M

where r < = n.

Is there an efficient algorithm to solve this problem ?

Answer 1

Note that the "first" binomial coefficient for fixed n is nC0. Let f(n) = nC0 + nC1 + ... + nC(r-1). Using the "Pascal's triangle" identity, nCk = (n-1)C(k-1) + (n-1)Ck we have

    nC0 + nC1 + nC2 + ... + nC(r-1)
    = (n-1)C(-1) + (n-1)C0 + (n-1)C0 + (n-1)C1 + (n-1)C1 + (n-1)C2 + ... + (n-1)C(r-2) + (n-1)C(r-1) 
    = 2[(n-1)C0 + (n-1)C1 + (n-1)C2 + ... + (n-1)C(r-2)] + (n-1)C(r-1)
    = 2[(n-1)C0 + ... + (n-1)C(r-1)] - (n-1)C(r-1),
    

i.e., f(n) = 2f(n-1) - (n-1)C(r-1) so each of the sums can be computed from the previous by doubling the previous and subtracting (n-1)C(r-1).

For example, if r=3, then

    f(0) = 1, 
    f(1) = 1 + 1      =  2 = 2f(0) - 0C2, 
    f(2) = 1 + 2 +  1 =  4 = 2f(1) - 1C2,
    f(3) = 1 + 3 +  3 =  7 = 2f(2) - 2C2,
    f(4) = 1 + 4 +  6 = 11 = 2f(3) - 3C2,
    f(5) = 1 + 5 + 10 = 16 = 2f(4) - 4C2,
    

and so on.

To perform the calculations mod m, you would need to pre-calculate the binomial coefficients (n-1)C(r-1) mod m. If m is prime, the binomial coefficients mod m are cyclic with cycle m^k (the power of m greater than r-1). If m is a power of a prime, the results are rather more complicated. (See http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf.) If m has more than one prime factor, the calculations can be reduced to the previous cases using the Chinese Remainder Theorem.