516 views
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}⌉$.
recategorized | 516 views

$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)

selected
0
Nice explanation.Thank you sir. :)

1
2