# Find sum of even index binomial coefficients

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
4C0 + 4C2 + 4C4
= 1 + 6 + 1
= 8

Input : n = 6
Output : 32
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1: (Brute Force)
The idea is to find all the binomial coefficient and find only the sum of even indexed value.

## CPP

 `// CPP Program to find sum  ` `// of even index term ` `#include ` `using` `namespace` `std; ` ` `  `// Return the sum of  ` `// even index term ` `int` `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 Program ` `int` `main() ` `{ ` `    ``int` `n = 4; ` `    ``cout << evenSum(n) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java Program to find sum  ` `// of even index term ` `import` `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 term ` `import` `math  ` ` `  `# Return the sum of even index term ` `def` `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 method ` `n ``=` `4` `print` `evenSum(n) ` ` `  ` `  `# This code is contributed by 'Gitanjali'. `

## C#

 `// C# Program to find sum  ` `// of even index term ` `using` `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

 ` `

Output :

```8
```

Time Complexity : O(n2)

Method 2: (Using Formula)
Sum of even indexed binomial coeffient : 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 ` `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)); ` `} ` ` `  `/* Drier 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 Code ` `public` `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 Coefficient ` `import` `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 method ` `if` `__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

 ` `

Output :

```8
```

Time Complexity : 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.