0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Assume that $88(2^k)-8k-80$ instructions are executed for an array of length $k$ for all $k\in\{0, ..., j\}$. Using this, show that $88(2^{j+1})-8(j+1)-80$ instructions are executed for an array of length $j+1$. $\endgroup$ – Shuri2060 Aug 24 '17 at 22:36
  • $\begingroup$ That's a misleading wording. It's not a "total" of $8n+64$ instructions if there are more instructions in the recursive call. And if it executes that many instructions for an array of length $n$, without specifying a range for $n$ (e.g. $n \gt 0$), then that statement is contradicted by the $8$ instructions for an array of length $0$. Just a badly worded question all around. $\endgroup$ – Wildcard Aug 24 '17 at 22:37
  • $\begingroup$ @Shuri2060 So, we manipulate $88(2^k)-8k-80$ into $P(k+1)$ (or j in your instance)? Is there some method of approach to this or any tips you can give? Also, are there any books or videos you'd recommend to get more familiar with these types of induction problems? $\endgroup$ – Xesiius Aug 24 '17 at 23:12
  • $\begingroup$ Not quite - if you do only that, then it's non-strong induction. You need to use all cases of $k=0, ..., j$ to prove $j+1$. It's hard to recommend problems... but perhaps simply typing in 'induction' into the MSE search box would give a number of examples+answers which may help? $\endgroup$ – Shuri2060 Aug 24 '17 at 23:20
  • 1
    $\begingroup$ $P$ is not a function here, but a statement. An example: let $P(n)\equiv$ '$2n$ is even'. Then in an inductive proof, you would prove $P(k)\implies P(k+1)$ in the inductive step (EVEN+EVEN=EVEN would be the argument here). $\endgroup$ – Shuri2060 Aug 24 '17 at 23:25
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.