Missed A2

Since I have missed my 2nd assignment of the course, I will do Q2 here instead

P(n): for every positive integer m, if m < n then T(m) ≤ T(n)
Using complete induction prove that P(n) holds for all integers n ≥ 1
Let k be an arbitrary integer such that k ≥ 1. Now suppose that P(β) holds for all integers β such that 1 ≤ β < k.
Then prove that P(k) holds as well.
By cases:
Case 1. k = 1. P(1) holds trivially since there is no positive integer m < 1.
Case 2. k = 2. T(1) and T(2)
T(1) = 1
T(2) = 1 + max{T(1), T(1)} = 1 + T(1) = 2
Since T(1) < T(2) then P(2) holds!
Case 3. k > 2.
In this case, 1 ≤ (k – 1) < k and, by Lemma 3.3 (in the course notes), 1 ≤ ⌊k/2⌋ ≤ ⌈k/2⌉ < k.
Therefore, by induction hypothesis, P(k − 1), P(⌊k/2⌋) and P(⌈k/2⌉) all hold. Since P(k − 1) holds, to prove that P(k) holds as well, it suffices to prove that T(k − 1) ≤ T(k).
So,
T(k – 1) = 1 + max{ T(⌈(k-1)/2⌉),
T(⌊(k-1)/2⌋) }
≤ 1 + max{ T(⌈k/2⌉), T(⌊k/2⌋) }
= T(k)
T(k – 1) ≤ T(k)