C++ Data Structure Recursion Sketch Inductive Proof (by using some values) The f

Question

C++ Data Structure

Recursion

Sketch Inductive Proof (by using some values)

The function that computes the sum of all even numbers less than or equal to n:

(1) Sketch an inductive proof that your function in (1) is correct. ((ex) Base case:~~, Inductive case:~~)

-------------------------------------------------------------------------------------

Recursively implement multiplication of two unsigned ints, a and b, using only addition. If you use *, you get no credit. Assume that a >= 0. (Hint: think about multiplication as repeated addition.):

(2) Sketch an inductive proof that your function in (2) is correct.

int sum evens (un signed int n) if (n 0) base case return 0; else if (n s 2 0) return n sum evens (n 2) else return sum evens (n 1);

Explanation / Answer

1.)

Proof With Induction:

Base Case(Initial step): sum_evens(0)= 0

Inductive case(step): sum_evens(1)= 0

sum_evens(2)= 2

sum_evens(3)= 2

sum_evens(4)= 2+4= 6

sum_evens(k)= 2(1+2+....k)=

sum_evens(n)= 2(1+2+3+4+....+n/2)= 2*(n/2((n/2)+1))/2= n/2((n/2)+1)

This means that, the first equality is a consequence of the inductive assumption.

By using values:

Suppose sum_evens(13) is called

If we see the program, the base case is if(n==0)

which will be the terminating condition for given recursive program.

Let's calculate sum_evens(13) manually so that we can verify our inductive proof when the function terminates.

since the program is to sum all the even numbers the output will be= 12+10+8+6+4+2= 40

Now, sum_evens(13) will check for base condition if(n==0); condition fails

control will goto else block if(n%2==0); here also condition fails

control will goto next else block, condition true; sum_evens(n-1)

Now sum_evens(12) will be called

first condition failed, next condition 12+sum_evens(10), from now onwards the function will recursively call sum_evens until n becomes 0

So it will look like, 12+10+8+6+4+2 and now when sum_evens(0) will be called it will return 0

and the output will be 12+10+8+6+4+2+0= 40.

2.)

Proof With Induction:

Base Case(Initial step):

multiply(a, 1)= 1 or multiply(1, b)= 1

Inductive case(step):

multiply(a, 1)= a

multiply(a, 2)= a+a= 2a

multiply(a, 3)= a+a+a= 3a

multiply(a, 4)= a+a+a+a= 4a

multiply(a, k)= a+a+a+.....+a(k times)= ka

multiply(a, n)= n*a.

and multiply(n, n)= n*n= n2

This means that, the first equality is a consequence of the inductive assumption.

By using values:

Here we can see base case is when a or b any of them have become 1;

then 1 will be returned by recursive call, the condition if(a==0||b==0) is given only to check if any of the input is 0 then the multiplication result will be 0.

Now let's call multiply(5, 3) to check whether it is producing the expected results.

On first three blocks the condition will be failed,

and the control will come to last else condition i.e. return a+ multiply(a, b-1)

where 5+multiply(5, 2) will be called

then 5+5+multiply(5, 1) will be called,

Now one of the input have become 1, so the called function will return 1 from if(b==1) block

so our solution will look like after returning, 5+5+5= 15.

and we already know that 5*3= 15

So both the functions are correct.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.