The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
416 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}⌉$.
asked in Set Theory & Algebra by Veteran (59.5k points)
recategorized by | 416 views

1 Answer

+11 votes
Best answer

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

answered by Veteran (353k points)
selected by
0
Nice explanation.Thank you sir. :)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,111 questions
44,694 answers
127,236 comments
43,753 users