Help me finish this induction problem. The induction proof needs to appeal to the code/function that is inside the box. So that means, don't just prove the given closed form mathmatically. You need to refer to the function foo as you prove the induction.

void foo(int n) print("tick"); foo (n-1); foo (n-1); Prove that for all n 20,foo(n) results in 2A(n+1) - 1 ticks being printed Base case: n 0 Plugging in n into formula prints 1 tick in foo(n): 2A(n+1)-1 21-1-1 Inductive step: Assume that n-k is true for some integer k 20 Show work here.. Prove that n k+1 is true for some int k 2 0, foo(k+1) results in 2A(k+2) - 1 ticks being printed Show work here