/***************************************
 Write a program that reads in a
 number n and prints out the sum
 as k goes from 0 to n of "n choose
 k".
              n*(n-1)*...*(n - k + 1)
 n choose k = -----------------------
                  k*(k-1)*...*2*1 

 Note: If k is 0 then n choose k is 1.
 Note: If k is n then n choose k is 1.
****************************************/
#include <iostream>
using namespace std;

int main()
{
  // Get n from user
  int n;
  cout << "Please enter n: ";
  cin >> n;

  // Compute sum
  int sum = 0;
  for(int k = 0; k <= n; k++)
  {
    // compute numerator of n choose k
    int num = 1;
    for(int m = n; m > n - k; m--)
      num = num*m;

    // compute denominator of n choose k
    int den = 1;
    for(int i = 1; i <= k; i++)
      den = den*i;

    // add value of n choose k to sum
    sum = sum + num/den;
  }

  // Write value of sum
  cout << "Sum as k goes from 0 to " << n
       << " is " << sum << endl;

  return 0;
}