Hi,

I'm not sure I understand the question, but I hope my answer will clarify things..

To prove the correctness, you have to explain what your recursive function means and how you arrived at it, as well as providing any explanation that may be necessary to the other parts of the solution.

It varies from solution to solution, but depending on what is obvious and what isn't, you may have to explain different things.

For example, in the question with the genie, I think the only thing I would add to the actual equations is the explanation of what the recursive function is, and how I got it. That is, I would write: if we throw the lamp from floor i, then we need ….. more throws if it breaks and ….. throws if it doesn't. We will choose the floor that minimizes the maximum of these, and so c(l,k)=…..".

If you are unsure, you should probably just do the steps 1-5 that we did in class, and after each step write "because….". If you cannot think of anything other than "it's so obvious anything I write here will be ridiculous", erase the "because", otherwise, write down why.