# CLRS Rod Cutting Inductive proof

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.

• 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. – D.W. Nov 10 '15 at 21:10
• 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. – D.W. Nov 10 '15 at 21:12
• 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. – kentilla Nov 10 '15 at 21:13

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.