Tutorialspoint.dev

Sum of Binomial coefficients

Given a positive integer n, the task is to find the sum of binomail coefficient i.e

nC0 + nC1 + nC2 + ……. + nCn-1 + nCn

Examples:

Input : n = 4
Output : 16
4C0 + 4C1 + 4C2 + 4C3 + 4C4
= 1 + 4 + 6 + 4 + 1
= 16

Input : n = 5
Output : 8



Method 1 (Brute Force):
The idea is to evaluate each binomial coefficient term i.e nCr, where 0 <= r <= n and calculate the sum of all the terms.

Below is the implementation of this approach:

C++

// CPP Program to find the sum of Binomial
// Coefficient.
#include <bits/stdc++.h>
using namespace std;
  
// Returns value of Binomial Coefficient Sum
int binomialCoeffSum(int n)
{
    int C[n + 1][n + 1];
  
    // Calculate value of Binomial Coefficient
    // in bottom up manner
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, n); j++) {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
  
            // Calculate value using previously
            // stored values
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
  
    // Calculating the sum.
    int sum = 0;
    for (int i = 0; i <= n; i++)
        sum += C[n][i];
  
    return sum;
}
  
/* Driver program to test above function*/
int main()
{
    int n = 4;
    printf("%d", binomialCoeffSum(n));
    return 0;
}

Java

// Java Program to find the sum 
// of Binomial Coefficient.
  
class GFG {
      
    // Returns value of Binomial 
    // Coefficient Sum
    static int binomialCoeffSum(int n)
    {
        int C[][] = new int[n + 1][n + 1];
      
        // Calculate value of Binomial 
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= Math.min(i, n); j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
      
                // Calculate value using previously
                // stored values
                else
                    C[i][j] = C[i - 1][j - 1] +
                              C[i - 1][j];
              
                  
            }
        }
      
        // Calculating the sum.
        int sum = 0;
        for (int i = 0; i <= n; i++)
            sum += C[n][i];
      
        return sum;
    }
      
    /* Driver program to test above function*/
    public static void main(String[] args)
    {
        int n = 4;
        System.out.println(binomialCoeffSum(n));
    }
}
  
// This code is contributed by prerna saini.

Python3

# Python  Program to find the sum 
# of Binomial Coefficient.
   
import math    
   
# Returns value of Binomial 
# Coefficient Sum
def binomialCoeffSum( n):
      
        C = [[0]*(n+2) for i in range(0,n+2)]
       
        # Calculate value of Binomial 
        # Coefficient in bottom up manner
        for i in range(0,n+1):
            for j in range(0, min(i, n)+1):
              
                # Base Cases
                if (j == 0 or j == i):
                    C[i][j] = 1
       
                # Calculate value using previously
                # stored values
                else:
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
       
        # Calculating the sum.
        sum = 0
        for i in range(0,n+1):
            sum += C[n][i]
       
        return sum
      
       
# Driver program to test above function
n = 4
print(binomialCoeffSum(n))
  
# This code is contributed by Gitanjali.

C#

// C# program to find the sum
// of Binomial Coefficient.
using System;
  
class GFG {
  
    // Returns value of Binomial
    // Coefficient Sum
    static int binomialCoeffSum(int n)
    {
        int[, ] C = new int[n + 1, n + 1];
  
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++) 
        {
            for (int j = 0; j <= Math.Min(i, n); j++) 
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i, j] = 1;
  
                // Calculate value using previously
                // stored values
                else
                    C[i, j] = C[i - 1, j - 1] + C[i - 1, j];
            }
        }
  
        // Calculating the sum.
        int sum = 0;
        for (int i = 0; i <= n; i++)
            sum += C[n, i];
  
        return sum;
    }
  
    /* Driver program to test above function*/
    public static void Main()
    {
        int n = 4;
        Console.WriteLine(binomialCoeffSum(n));
    }
}
  
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find the 
// sum of Binomial Coefficient.
// Returns value of Binomial 
// Coefficient Sum
  
function binomialCoeffSum($n)
{
    $C[$n + 1][$n + 1] = array(0);
  
    // Calculate value of 
    // Binomial Coefficient
    // in bottom up manner
    for ($i = 0; $i <= $n; $i++) 
    {
        for ($j = 0;
             $j <= min($i, $n); $j++)
        {
            // Base Cases
            if ($j == 0 || $j == $i)
                $C[$i][$j] = 1;
  
            // Calculate value 
            // using previously
            // stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] + 
                             $C[$i - 1][$j];
        }
    }
  
    // Calculating the sum.
    $sum = 0;
    for ($i = 0; $i <= $n; $i++)
        $sum += $C[$n][$i];
  
    return $sum;
}
  
// Driver Code
$n = 4;
echo binomialCoeffSum($n);
  
// This code is contributed by ajit
?>


Output:

16

Method 2 (Using Formula):

This can be proved in 2 ways.
First Proof: Using Principle of induction.

For basic step, n = 0
LHS = 0C0 = (0!)/(0! * 0!) = 1/1 = 1.
RHS= 20 = 1.
LHS = RHS

For induction step:
Let k be an integer such that k > 0 and for all r, 0 <= r <= k, where r belong to integers,
the formula stand true.
Therefore,
kC0 + kC1 + kC2 + ……. + kCk-1 + kCk = 2k

Now, we have to prove for n = k + 1,
k+1C0 + k+1C1 + k+1C2 + ……. + k+1Ck + k+1Ck+1 = 2k+1

LHS = k+1C0 + k+1C1 + k+1C2 + ……. + k+1Ck + k+1Ck+1
(Using nC0 = 0 and n+1Cr = nCr + nCr-1)
= 1 + kC0 + kC1 + kC1 + kC2 + …… + kCk-1 + kCk + 1
= kC0 + kC0 + kC1 + kC1 + …… + kCk-1 + kCk-1 + kCk + kCk
= 2 X ∑ nCr
= 2 X 2k
= 2k+1
= RHS

Second Proof: Using Binomial theorem expansion

Binomial expansion state,
(x + y)n = nC0 xn y0 + nC1 xn-1 y1 + nC2 xn-2 y2 + ……… + nCn-1 x1 yn-1 + nCn x0 yn

Put x = 1, y = 1
(1 + 1)n = nC0 1n 10 + nC1 xn-1 11 + nC2 1n-2 12 + ……… + nCn-1 11 1n-1 + nCn 10 1n

2n = nC0 + nC1 + nC2 + ……. + nCn-1 + nCn

Below is implementation of this approach:

C++

// CPP Program to find sum of Binomial
// Coefficient.
#include <bits/stdc++.h>
using namespace std;
  
// Returns value of Binomial Coefficient Sum
// which is 2 raised to power n.
int binomialCoeffSum(int n)
{
    return (1 << n);
}
  
/* Drier program to test above function*/
int main()
{
    int n = 4;
    printf("%d", binomialCoeffSum(n));
    return 0;
}

Java

// Java Program to find sum 
// of Binomial Coefficient.
import java.io.*;
  
class GFG
{
    // Returns value of Binomial
    // Coefficient Sum which is 
    // 2 raised to power n.
    static int binomialCoeffSum(int n)
    {
        return (1 << n);
    }
  
    // Driver Code
    public static void main (String[] args) 
    {
        int n = 4;
        System.out.println(binomialCoeffSum(n));
    }
}
  
// This code is contributed 
// by akt_mit.

Python3

# Python  Program to find the sum 
# of Binomial Coefficient.
   
import math     
# Returns value of Binomial 
# Coefficient Sum
def binomialCoeffSum( n):
      
    return (1 << n);
  
# Driver program to test
# above function
n = 4
print(binomialCoeffSum(n))
  
# This code is contributed
# by Gitanjali.

C#

// C# Program to find sum of 
// Binomial Coefficient.
using System;
  
class GFG {
  
    // Returns value of Binomial Coefficient Sum
    // which is 2 raised to power n.
    static int binomialCoeffSum(int n)
    {
        return (1 << n);
    }
  
    /* Drier program to test above function*/
    static public void Main()
    {
        int n = 4;
        Console.WriteLine(binomialCoeffSum(n));
    }
}
  
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find sum 
// of Binomial Coefficient.
  
// Returns value of Binomial 
// Coefficient Sum which is 
// 2 raised to power n.
function binomialCoeffSum($n)
{
    return (1 << $n);
}
  
// Driver Code
$n = 4;
echo binomialCoeffSum($n);
  
// This code is contributed
// by akt_mit
?>


Output:

16


This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter