Suppose that you have a recursive function which accepts an array as input. When its called with an array of length $n$, it executes a total of $8n + 64$ instructions, two of which are recursive function calls with an array of size $n-1$, and when called with an array of length $0$, it executes $8$ instructions. Prove that the function executes $88(2^n)-8n-80$ instructions when its input has length $n$, for all $n \geq 0$ .
I understand the steps in an inductive proof. First, the base case is proven. Then the inductive hypothesis is stated and assumed to be true for the constraints $P(k)$. Then we use this to show in our inductive step that our $P(k+1)$ is also true.
In the case of this problem, since it's recursive I assume we will be using strong induction. In which case, we essentially work backwards in our proof. However, I don't know where to take it after I've proven the base case. Maybe it's the wording that's throwing me off, but I can't figure out how to go about this. Thanks.
When you say "$8n+64$ instructions two of which are recursive function calls with an array of size $n-1$", I'll assume you mean $8n+64$ instructions as well as two recursive $n-1$ calls.
In this case, no strong induction is necessary. All we need for a base case in $n=0$, which can be verified algebraically.
Now we assume $P(k)$ holds, and consider $P(k+1)$. We know that for $n=k+1$, the function call executes $8(k+1)+64$ instructions as well as two recursive calls with $n=k$. From $P(k)$, we know the total is thus $8(k+1)+64+2[88(2^k)-8k-80]$, which we can rearrange into $88(2^{k+1})-8(k+1)-80$. This implies $P(k+1)$ holds. We can therefore claim proof by simple induction.