PROBLEM 2: Consider a finite set S with n elements; the number of distinct subsets of S with exactly two is called "n choose 2" and typically written as n2. You may Recall that n2=n(n-1)2.

Below is a (trivial) C++ function which takes a non-negative integer n and returns n2 (also a non-negative integer):

unsigned int n_choose_2(unsigned int n) {

if(n==0)

return 0;

else

return n*(n-1)/2;

}

Your job: write a function which also returns n2 but with the following constraints:

• You cannot use the multiplication operator *

• You cannot use the division operator /

• You cannot have any loops

• You cannot add any additional parameters to the function

• Your function must be self-contained: no helper functions!

• You cannot use any globals

• You cannot use any static variables

• You cannot use any "bit twiddling" operations -- no shifts, etc.

However,

• You can use recursion

• You can use the + and - operators.

You will submit a scanned hardcopy (hand-written or printed) or pdf via gradescope. Of course, you are free to try out your solution in a real program.

In addition: argument of correctness required!

You must explain the logic of your solution! In other words, explain why it works. Think in terms of an inductive argument.

Just giving a correct C++ function is not sufficient and will not receive many points (possibly zero!)

Another note: an example is not an argument of correctness!