Regarding the proof for even case

#1

how can we say that the cost to reach n from n+1 is always greater compared to other cases

#2

@hv439606,
Cost to reach n from n+1 is not always greater than other cases, for eg if you go from (n+1)/2 -> n+1 -> n
This could be smaller than other cases depending on x,y,z.
But one thing we can be sure of is that {some previous state} -> n -> n+1 -> n would always be greater {some previous state} -> n

#3

Oh…sorry I meant for the even case…
Like whats the proof for even case

#4

@hv439606,
If n is even, then (n+1) is odd, then there is no way to reach (n+1)/2 -> (n+1), so the only optimum way to reach (n+1) is
{some_previous_state} -> n -> (n+1)
In which case, going back to n would only increase the cost of reaching n.

#5

So instead of reaching n+1 y can’t I reach n+2 and decrement 2 steps (say the doubling and decrement costs are minimum)

#6

@hv439606,
Cost_1 = {(n / 2) -> (n) } = x
Cost_2 = {((n + 2) / 2) -> (n + 2) -> (n + 1) -> (n)} = x + z + z

Breaking news!!! (x + 2*z) > x for all x,z belongs to N

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.