recategorized by
1,539 views

1 Answer

Best answer
20 votes
20 votes

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

Related questions

11 votes
11 votes
3 answers
1
Kathleen asked Oct 8, 2014
1,490 views
Prove using mathematical induction for $n \geq 5, 2^n n^2$
28 votes
28 votes
3 answers
3
Kathleen asked Sep 14, 2014
4,069 views
Let $S= \{0, 1, 2, 3, 4, 5, 6, 7\}$ and $⊗$ denote multiplication modulo $8,$ that is, $x ⊗ y= (xy) \mod 8$Prove that $( \{ 0, 1\}, ⊗)$ is not a group.Write three d...
60 votes
60 votes
6 answers
4
Kathleen asked Sep 14, 2014
13,357 views
Let $P(S)$ denotes the power set of set $S.$ Which of the following is always true?$P(P(S)) = P(S)$$P(S) ∩ P(P(S)) = \{ Ø \}$$P(S) ∩ S = P(S)$$S ∉ P(S)$