Please use C++!

We want to write a recursive solution for and prove that it is correct where n >= 1

• What is the base case?
• Prove that the recursive case for this function is correct

eq(int n) {

// base case here ....

// recursive case here

return n * pow(2, n) + eq(n-1)

* 2' = 2 + ( 1) 21+1 21. -1 i= We want to write a recursive solution for Xi * 21 = 2 + (n - 1)* 2" and prove that it is correct where n >= 1 What is the base case? Prove that the recursive case for this function is correct eq(int n) { // base case here // recursive case here return n * pow(2, n) + eq(n-1) Step 1: Identify base case Step 2: Identify Inductive Hypothesis (eg, substitute k for n in the equation) Step 3: Write down the implementation, substituting (k+1) for n Step 4: Write down (further down on the page) what you want to end up at (eg, plug (k+1) in for the equation you're proving is equal to the implementation 2 + (n-1) 2n+1 Step 5: Use mathematical properties to get from Step 4 to Step 5 using Step 2 as necessary