Binomial Sum#11488

Binomial Sum (Editorial)

Rewrite the sum in the form:

1 \cdot C_{n}^{0} + 2 \cdot C_{n}^{1} + 3 \cdot C_{n}^{2} + ... + (n + 1) \cdot C_{n}^{n} =

1 \cdot C_n^0 + 2 \cdot C_n^1 + 3 \cdot C_n^2 + ... + (n + 1) \cdot C_n^n =

(C_{n}^{0} + C_{n}^{1} + C_{n}^{2} + ... + C_{n}^{n}) + 1 \cdot C_{n}^{1} + 2 \cdot C_{n}^{2} + ... + n \cdot C_{n}^{n}

\left( C_n^0 + C_n^1 + C_n^2 + ... + C_n^n \right) + 1 \cdot C_n^1 + 2 \cdot C_n^2 + ... + n \cdot C_n^n

The sum in parentheses is $2^{n}$ 2^n. If in Newton’s binomial formula

(a + b)^{n} = i = 0 \sum n C_{n}^{i} a^{i} b^{n - i}

(a + b)^n = \sum_{i=0}^n{C_n^ia^ib^{n-i}}

we set $a = b = 1$ a = b = 1, then we get the relation: $(1 + 1)^{n} = \sum_{i = 0}^{n} C_{n}^{i} 1^{i} 1^{n - i}$ (1 + 1)^n = \sum_{i=0}^n{C_n^i1^i1^{n-i}}, or

2^{n} = i = 0 \sum n C_{n}^{i} = C_{n}^{0} + C_{n}^{1} + ... + C_{n}^{n}

2^n = \sum_{i=0}^nC_n^i = C_n^0 + C_n^1 + ... + C_n^n

Let’s compute the remaining sum:

1 \cdot C_{n}^{1} + 2 \cdot C_{n}^{2} + ... + n \cdot C_{n}^{n} =

1 \cdot C_n^1 + 2 \cdot C_n^2 + ... + n \cdot C_n^n =

1 \cdot \frac{n !}{1 ! \cdot ( n - 1 )!} + 2 \cdot \frac{n !}{2 ! \cdot ( n - 2 )!} + ... + n \cdot \frac{n !}{n ! \cdot ( n - n )!} =

1 \cdot {n! \over 1! \cdot (n - 1)!} + 2 \cdot {n! \over 2! \cdot (n - 2)!} + ... + n \cdot {n! \over n! \cdot (n - n)!} =

n \cdot (\frac{( n - 1 )!}{0 ! \cdot ( n - 1 )!} + \frac{( n - 1 )!}{1 ! \cdot ( n - 2 )!} + ... + \frac{( n - 1 )!}{( n - 1 )! \cdot ( n - n )!}) =

n \cdot \left( {(n - 1)! \over 0! \cdot (n - 1)!} + {(n - 1)! \over 1! \cdot (n - 2)!} + ... + {(n - 1)! \over (n - 1)! \cdot (n - n)!} \right) =

n \cdot (C_{n - 1}^{0} + C_{n - 1}^{1} + ... + C_{n - 1}^{n - 1}) = n \cdot 2^{n - 1}

n \cdot \left( C_{n-1}^0 + C_{n-1}^1 + ... + C_{n-1}^{n-1} \right) = n \cdot 2^{n - 1}

So the answer is $2^{n} + n \cdot 2^{n - 1} = (n + 2) \cdot 2^{n - 1}$ 2^n + n \cdot 2^{n - 1} = (n + 2) \cdot 2^{n - 1}.

Example

Compute the value for $n = 3$ n = 3. For direct calculation:

1 \cdot C_{3}^{0} + 2 \cdot C_{3}^{1} + 3 \cdot C_{3}^{2} + 4 \cdot C_{3}^{3} = 1 \cdot 1 + 2 \cdot 3 + 3 \cdot 3 + 4 \cdot 1 = 1 + 6 + 9 + 4 = 20

1 \cdot C_3^0 + 2 \cdot C_3^1 + 3 \cdot C_3^2 + 4 \cdot C_3^3 = 1 \cdot 1 + 2 \cdot 3 + 3 \cdot 3 + 4 \cdot 1 = 1 + 6 + 9 + 4 = 20

When calculated using the formula: $5 \cdot 2^{2} = 20$ 5 \cdot 2^2 = 20.

Algorithm implementation

Read the input value of $n$ .

scanf("%lld", &n);

Compute and print the answer.

res = (1LL << (n - 1)) * (n + 2);
printf("%lld\n", res);

Algorithm implementation — function

Declare an array to store the results: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

int dp[31][31];

The Cnk function computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k.

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % 9929;
}

C++

The main part of the program. Read the input value of $n$ .

scanf("%d", &n);
memset(dp, -1, sizeof(dp));

Compute the required sum.

res = 0;
for (i = 0; i <= n; i++)
  res += (i + 1) * Cnk(n, i);

Print the answer.

printf("%d\n", res);

Python implementation — comb function

import math

Read the input value of $n$ .

n = int(input())

Compute the required sum. To compute the binomial coefficient, we’ll use the built-in function comb.

res = 0
for i in range(n + 1):
  res += (i + 1) * math.comb(n, i)

Print the answer.

print(res)

Python implementation — function

The Cnk function computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k.

def Cnk(n, k, dp):
  if n == k: return 1
  if k == 0: return 1
  if dp[n][k] != -1: return dp[n][k]
  dp[n][k] = Cnk(n - 1, k - 1, dp) + Cnk(n - 1, k, dp)
  return dp[n][k]

The main part of the program. Read the input value of $n$ .

n = int(input())

Initialize all the elements of the two-dimensional list dp with the value $- 1$ . We shall use this list to memoize the results: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

dp = [[-1 for _ in range(31)] for _ in range(31)]

Compute the required sum.

res = 0
for i in range(n + 1):
   res += (i + 1) * Cnk(n, i, dp)

Print the answer.

print(res)

Python implementation — formula

Read the input value of $n$ .

n = int(input())

Compute the answer $r es$ using the formula.

res = (1 << (n - 1)) * (n + 2)

Print the answer.

print(res)