Redaksiya

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} =

(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}

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

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

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

2^{n} = i = 0 \sum n C_{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 \frac{n !}{1 ! \cdot ( n - 1 )!} + 2 \cdot \frac{n !}{2 ! \cdot ( n - 2 )!} + ... + n \cdot \frac{n !}{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 (C_{n - 1}^{0} + C_{n - 1}^{1} + ... + C_{n - 1}^{n - 1}) = n \cdot 2^{n - 1}

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

Example

Compute the value for $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

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

Algorithm realization

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 realization – function

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

int dp[31][31];

The Cnk function computes the value of the binomial coefficient $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;
}

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 realization – 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 realization – function

The Cnk function computes the value of the binomial coefficient $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 = [[-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 realization – formula

Read the input value of $n$ .

n = int(input())

Compute the answer $res$ using the formula.

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

Print the answer.

print(res)