Given a positive integer n. The task is to find the sum of even indexed binomial coefficient. That is,
nC0 + nC2 + nC4 + nC6 + nC8 + ………..
Examples :
Input : n = 4
Output : 8
Explanation:
4C0 + 4C2 + 4C4
= 1 + 6 + 1
= 8Input : n = 6
Output : 32
Method 1: (Brute Force)
The idea is to find all the binomial coefficients and find only the sum of even indexed values.
CPP
// CPP Program to find sum // of even index term#include <bits/stdc++.h>using namespace std;// Return the sum of // even index termint evenSum(int n){ int C[n + 1][n + 1]; int i, j; // 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]; } } // finding sum of even index term. int sum = 0; for (int i = 0; i <= n; i += 2) sum += C[n][i]; return sum;}// Driver Programint main(){ int n = 4; cout << evenSum(n) << endl; return 0;} |
Java
// Java Program to find sum // of even index termimport java.io.*;import java.math.*;class GFG { // Return the sum of // even index term static int evenSum(int n) { int C[][] = new int [n + 1][n + 1]; int i, j; // Calculate value of Binomial // Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.min(i, n); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // else Calculate value using // previously stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } // finding sum of even index term. int sum = 0; for (i = 0; i <= n; i += 2) sum += C[n][i]; return sum; } // Driver Program public static void main(String args[]) { int n = 4; System.out.println(evenSum(n)); }}/*This code is contributed by Nikita Tiwari.*/ |
Python
# Python Program to find sum of even index termimport math # Return the sum of even index termdef evenSum(n) : # Creates a list containing n+1 lists, # each of n+1 items, all set to 0 C = [[0 for x in range(n + 1)] for y in range(n + 1)] # 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] # Finding sum of even index term sum = 0; for i in range(0, n + 1): if n % 2 == 0: sum = sum + C[n][i] return sum # Driver methodn = 4print evenSum(n)# This code is contributed by 'Gitanjali'. |
C#
// C# Program to find sum // of even index termusing System;class GFG { // Return the sum of // even index term static int evenSum(int n) { int [,]C = new int [n + 1,n + 1]; int i, j; // Calculate value of Binomial // Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.Min(i, n); j++) { // Base Cases if (j == 0 || j == i) C[i,j] = 1; // else Calculate value using // previously stored values else C[i,j] = C[i - 1,j - 1] + C[i - 1,j]; } } // finding sum of even index term. int sum = 0; for (i = 0; i <= n; i += 2) sum += C[n,i]; return sum; } // Driver Program public static void Main() { int n = 4; Console.WriteLine(evenSum(n)); }}/*This code is contributed by vt_m.*/ |
PHP
<?php// PHP Program to find sum // of even index term// Return the sum of // even index termfunction evenSum($n){ $C = array(array()); $i; $j; // 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 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]; } } // finding sum of even index term. $sum = 0; for ( $i = 0; $i <= $n; $i += 2) $sum += $C[$n][$i]; return $sum;}// Driver Code$n = 4;echo evenSum($n) ;// This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript Program to find sum // of even index term// Return the sum of // even index termfunction evenSum(n){ var C = Array.from(Array(n+1), ()=> Array(n+1).fill(0)); var i, j; // Calculate value of Binomial // Coefficient in bottom up manner for (i = 0; i <= n; i++) { for (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]; } } // finding sum of even index term. var sum = 0; for (var i = 0; i <= n; i += 2) sum += C[n][i]; return sum;}// Driver Programvar n = 4;document.write( evenSum(n) ); </script> |
Output
8
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Method 2: (Using Formula)
Sum of even indexed binomial coefficient : 
Proof :
We know, (1 + x)n = nC0 + nC1 x + nC2 x2 + ..... + nCn xn Now put x = -x, we get (1 - x)n = nC0 - nC1 x + nC2 x2 + ..... + (-1)n nCn xn Now, adding both the above equation, we get, (1 + x)n + (1 - x)n = 2 * [nC0 + nC2 x2 + nC4 x4 + .......] Put x = 1 (1 + 1)n + (1 - 1)n = 2 * [nC0 + nC2 + nC4 + .......] 2n/2 = nC0 + nC2 + nC4 + ....... 2n-1 = nC0 + nC2 + nC4 + .......
Below is the implementation of this approach :
C++
// CPP Program to find sum even indexed Binomial// Coefficient.#include <bits/stdc++.h>using namespace std;// Returns value of even indexed Binomial Coefficient// Sum which is 2 raised to power n-1.int evenbinomialCoeffSum(int n){ return (1 << (n - 1));}/* Driver program to test above function*/int main(){ int n = 4; printf("%d", evenbinomialCoeffSum(n)); return 0;} |
Java
// Java Program to find sum even indexed // Binomial Coefficient.import java.io.*;class GFG {// Returns value of even indexed Binomial Coefficient// Sum which is 2 raised to power n-1.static int evenbinomialCoeffSum(int n){ return (1 << (n - 1));}// Driver Codepublic static void main(String[] args){int n = 4; System.out.println(evenbinomialCoeffSum(n));} }// This code is contributed by 'Gitanjali'. |
Python
# Python program to find sum even indexed # Binomial Coefficientimport math # Returns value of even indexed Binomial Coefficient# Sum which is 2 raised to power n-1.def evenbinomialCoeffSum( n): return (1 << (n - 1))# Driver methodif __name__ == '__main__': n = 4 print evenbinomialCoeffSum(n)# This code is contributed by 'Gitanjali'. |
C#
// C# Program to find sum even indexed // Binomial Coefficient.using System;class GFG { // Returns value of even indexed // Binomial Coefficient Sum which // is 2 raised to power n-1. static int evenbinomialCoeffSum(int n) { return (1 << (n - 1)); } // Driver Code public static void Main() { int n = 4; Console.WriteLine(evenbinomialCoeffSum(n)); }}// This code is contributed by 'Vt_m'. |
PHP
<?php// PHP Program to find sum // even indexed Binomial// Coefficient.// Returns value of even indexed// Binomial Coefficient Sum which // is 2 raised to power n-1.function evenbinomialCoeffSum( $n){ return (1 << ($n - 1));} // Driver Code $n = 4; echo evenbinomialCoeffSum($n);// This code is contributed by anuj_67.?> |
Javascript
<script>// JavaScript Program to find sum even indexed // Binomial Coefficient.// Returns value of even indexed Binomial Coefficient// Sum which is 2 raised to power n-1.function evenbinomialCoeffSum(n){ return (1 << (n - 1));}// Driver code let n = 4; document.write(evenbinomialCoeffSum(n)); // This code is contributed by code_hunt.</script> |
Output
8
Time Complexity: O(1)
Auxiliary Space: O(1)
Sum of odd index binomial coefficient
Using the above result we can easily prove that the sum of odd index binomial coefficient is also 2n-1.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
