Question

For part 5B I already have 2^(n+1) -1, but I'm not sure how to prove it using induction. I am actually taking the prerequisite to this class concurrently and we haven't gotten to that part unfortunately so please show clear steps.

PROBLEM 5 Consider the recursive C function below: void foo (unsigned int n) cout << "tick" <<endl; if(n > ) { foo (n-1); foo(n-1) 5A: Complete the following table indicating how many "ticks" are printed for various parameters n. Unenforceable rule: derive your answers "by hand" -- not simply by writing a program calling the function. number of ticks printed when foo(n) is called 4 5.B Derive a conjecture expressing the number of ticks as a i.e., complete the following: function of n -- "Conjecture: for all n20, calling foo(n) results in being printed" ticks 5.C: Prove your conjecture from part B (hint: Induction!)

Answer 1

For induction we have to prove a base case and then we give a induction hypotheses and then we prove for inductive step

Here we can see that base case will be n=0 which gives 2^1 -1 =1 hence its correct

Induction hypotheses: Let's assume that this is true for some k

Inductive step: we have to prove this for k+1

So for K number of times, it will be printed is 2^(k+1)-1

According to our step for f(k+1), the result should be 2^(k+2)-1

And for k+1 we have 2 more calls to f(k) hence two times the number of ticks printed by f(k) and another one which is printed in f(k+1) itself so the total number becomes f(k+1)= 2*f(k)+1 times of we know that for f(k) it is

2^(k+1)-1 putting this value gives us f(k+1)=2^(k+2)-1

Hence this is true for any k