GATE CSE 2000 | Question: 3

Question

Consider the following sequence:

$s_1 = s_2 = 1$ and $s_i = 1 + \min  \left({s_{i-1}, s_{i-2}}\right) \text{ for } i > 2$.

Prove by induction on $n$ that $s_n=⌈\frac{n}{2}⌉$.

Answer 1

$s_3 = 1 + \min(s_1, s_2) \\= 1 + \min(1, 1) = 2 = \lceil \frac{3}{2} \rceil$.

So, base condition of induction satisfied. 

Assume, $s_{n-2} =\lceil \frac{n-2}{2} \rceil$ and $s_{n-1} =\lceil \frac{n-1}{2} \rceil$ (Induction hypothesis)

Now, we have to prove,

$s_n = \lceil \frac{n}{2} \rceil$

$s_n = 1 + \min(s_{n-1}, s_{n-2}) \\= 1 +  \lceil \frac{n-2}{2} \rceil \\= 1 +  \lceil \frac{n}{2} \rceil -1 \\=\lceil \frac{n}{2}\rceil$

(Hence, proved)

Comments

Nice explanation.Thank you sir. :)

---

Sequence is  1 1 2 2 3 3 4 4 5 5 6 6 7 7 ………

Sn is representing the nth element.

So, it will be ceil(n/2) for sure.