2
$\begingroup$

I'd like to preface this question by saying that it is not a homework question. However, it is a question regarding the course material. In the rod-cutting example an equation is presented to determine the maximum possible revenue attainable for give rod length:

$r_{n} = max(p_{i} + r_{n-i})$ (15.2)

I'm trying to prove by induction that this equation does in-fact output the optimal revenue.

It's stated that, "A simple induction on n proves that this answer is equal to the desired answer $r_{ n}$, using equation. 15.2"

While not required, I'm attempting to perform this induction and I'm stuck on the inductive step. Here is what I have so far:

Base Case n = 3, where $r_{n}$ represents the maximum revenue attainable from a rod of length $n$ (note the following references a price list p, which corresponds to the price of a rod for a given length, and a list r which corresponds to the maximum revenue given a rod length).

$i = 1, p_{1} + r_{3-1} = 6 $

$i = 2, p_{2} + r_{3-2} = 6 $

$i = 3, p_{3} + r_{3-3} = 8 $

Assume,
$r_{k} = max(p_{i} + r_{k-i})$

Inductive Step,
$r_{k+1} = max(p_{i} + r_{(k+1)-i})$

I'm am unclear on how to proceed from here. I realize that the optimal revenue for a give rod length is defined in terms the optimal revenue for smaller rod lengths, which I believe means this problem displays optimal sub-structure. But i'm unclear on how to proceed. I'm prefer to not be given an answer but rather some direction.

$\endgroup$
  • $\begingroup$ 1. Please edit your question to include the statement you are trying to prove, to make the question self-contained. I see you included a recurrence relation for $r_n$, and a claim that "this answer is equal to $r_n$", but you haven't shown us what "this answer" is. Are you trying to prove that some particular expression for $r_n$ is valid? Or are you trying to prove that the recurrence relation accurately characterizes the optimal solution to the rod-cutting problem? Either way, please make the question self-contained. $\endgroup$ – D.W. Nov 10 '15 at 21:10
  • $\begingroup$ 2. Is this a CS question or a math question? Proving something is true by induction sounds like a pure math question. We don't have a strict policy against pure math questions, but generally we'd expect the question to explain why it needs to be answered from a CS perspective. 3. Have you looked at the techniques in cs.stackexchange.com/q/2789/755? Not sure if they'll be helpful, because I'm not sure I understand what your particular question is. $\endgroup$ – D.W. Nov 10 '15 at 21:12
  • $\begingroup$ may strong induction be helpful? You are using n=3 as base case, but the bottom-up version of the algoritm starts with j=1. $\endgroup$ – kentilla Nov 10 '15 at 21:13
1
$\begingroup$

First, be more precise in your writing. What does $\max$ range over? What is $k$ in the inductive hypothesis and step? What is the actual statement in the induction hypothesis?

In the step, you want to establish that $r_n = \dots$ is optimal assuming all $r_k$ as computed by the proposed formula for $k \leq n$ are optimal, for some fixed $n \geq 3$.

One way you typically do this is by contradiction. Assume (in addition to IH) that $\max \dots$ were not optimal. Derive that the chosen $r_k$ is not optimal either, then, which is in contradiction with the IH.

$\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.