Define the sequence c0, c1, ... by the equationsC0 = 0, cn = c[n/2] + 3 for-all n > 0.W...

Define the sequence c0, c1, ... by the equations

C0 = 0, cn = c[n/2] + 3 for-all n > 0.

What is wrong with the following “proof” that cn ≤ 2n for all n ≥ 3? (You should verify that it is false that cn ≤ 2n for all n ≥ 3.)

We use the Strong Form of Mathematical Induction.

Basis Step (n = 3)

We have

c3 = c1 + 3 = (c0 + 3) + 3 = 6 ≤ 2.3.

The Basis Step is verified.

Inductive Step

Assume that ck ≤ 2k for all k < n. Then

cn = c[n/2] +3 ≤ 2[n/2] + 3 < 2(n/2)+3 = n+3 < n+n = 2n,

(Since 3 < n, n + 3 < n + n.) The Inductive Step is complete.