how can we prove that cost to reach i+1 is always greater than cost to reach i when i is even?
Cell mitosis issue
It is because i+1 will be odd since i is even. So we can only come from i , since we can’t divide i+1 by 2 so we are adding the cost of i and the cost of decrement from i+1 to i.
Since cost of i + cost of decrement>=cost of i
so we do not take this case
Please watch the video again for more clarity. It must be explained well there.
i agree with you in the case when we come to i+1 from i but how to know that when we come to i+1 through i+2 the cost we will be getting is still greater than cost to reach i?
1 Like
please answer the doubt
Say cost of doubling is x. And cost of decreasing by 1 is z.
Cost_1(when we reach n from n/2) = {(n / 2) -> (n) } = x
Cost_2 (when you reach n from (n+2)/2)= {((n + 2) / 2) -> (n + 2) -> (n + 1) -> (n)} = x + z + z
(x + z + z) > x for all x,z belongs to N
Hope this clears your doubt
1 Like
can i say that cost(to reach n)<=cost(to reach n+2)+2*decrement cost for every even natural number n in this question?and through this we can conclude that cost(to reach n)<=cost(to reach n+1)+z?
Yes…that only i proved above
Cost_1 should be = Cost(n/2) + x
Cost_2 should be = Cost(n+2/2) + x + z + z
You made an assumption that Cost(n/2), Cost(n+2/2) are equal.
Hope you get my proof!! 
For every even i the cost of coming from a backward direction will be more!!
No the assumption cost(n/2),cost(n+2/2) are equal is wrong if you have assumed it
But Cost(n+2/2) = cost(n/2)+y.
Hence the Cost_2 is obviously greater.
Hope i have cleared your doubt.