# 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, 2015 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, 2015 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. Nov 10, 2015 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.

I don't think the statement

A simple induction on $$n$$ proves that this answer is equal to the desired answer $$r_n$$, using equation. 15.2

means to use induction to prove

$$\begin{equation} r_n=\max_{1\le i \le n}(p_i+r_{n-i}) \end{equation}$$

but instead, it means to use induction to prove the algorithm:

CUT-ROD(p,n)
1 if n == 0
2     return 0
3 q = -∞
4 for i = 1 to n
5     q=max(q,p[i]+CUT-ROD(p,n-i))
6 return q


has the same result as $$r_n$$.

My proof is:

#Step0: A special case

$$CUT-ROD(p, 0) = r_0$$

#Step1:

$$\begin{eqnarray*} if \ n = 1, then \ CUT-ROD(p,1) &=& max(-\infty, p_1) = p_1\\ \because r_1 &=& p_1\\ \therefore CUT-ROD(p,1) &=& r_1 \end{eqnarray*}$$

#Step2: assume that

$$CUT-ROD(p,n-1) = r_{n-1}$$

further,

$$\begin{eqnarray*} CUT-ROD(p,n-1) &=& q_{n-1} = \max_{1 \le i \le n-1}(q_{i-1}, p_i+CUT-ROD(p, n-1-i))\\ r_{n-1} &=& \max_{1 \le i \le n-1}(p_i + r_{n-1-i})\\ \end{eqnarray*}$$

therefore,

$$\max_{1 \le i \le n-1}(q_{i-1}, p_i+CUT-ROD(p, n-1-i)) = \max_{1 \le i \le n-1}(p_i + r_{n-1-i})$$

#Step3: let's calculate

$$\begin{eqnarray*} CUT-ROD(p, n) &=& q_n\\ &=& \max_{1 \le i \le n}(q_{i-1}, p_i+CUT-ROD(p, n-i))\\ &=& \max (\max_{1 \le i \le n-1}(q_{i-1}, p_i+CUT-ROD(p, n-1-i)), p_n+CUT-ROD(p,n-n)) \end{eqnarray*}$$

Remember the result of #Step2, therefore we have $$\begin{eqnarray*} CUT-ROD(p, n) &=& \max (\max_{1 \le i \le n-1}(p_i + r_{n-1-i}), p_n+CUT-ROD(p,n-n))\\ &=& \max (\max_{1 \le i \le n-1}(p_i + r_{n-1-i}), p_n+r_{n-n})\\ &=& \max_{1 \le i \le n}(p_i + r_{n-i})\\ &=& r_n \end{eqnarray*}$$

q.e.d