I'd like to have a formal proof of the following case (case 2) related to the euclidean GCD algorithm:
We have M > N, and N > M/2, I'd like to show that M - N > M / 2.
Thank you!
Is this demonstration a valid one:
Let M, N € Z, M > N, and N > M / 2, show that M - N > M / 2:
Basis:
M = 1, N = 0 --> 1 - 0 > 1 / 2 --> 1 > 1 / 2 (TRUE)
Induction:
Assume true k = M, l = N
k - l > k / 2
l > k - k / 2
l > k / 2
You're right, Plato, let me rectify:
We have M > N, and N > M/2, I'd like to show that M - N < M / 2.
The actual statement that I want to prove is:
case 2: N > M/2. In this case the remainder would be M - N, and since N > M/2, M -
N would be less than M/2.
How would you write a formal proof ?