Solved: Define a sequence c1, c2, c3,..., recursively as follows: c1 = 0, ck = 2ck/2 +

Chapter 11, Problem 23

(choose chapter or problem)

Define a sequence \(c_{1}, c_{2}, c_{3}, \ldots\), recursively as follows:

\(c_{1}=0\),

\(c_{k}=2 c_{\lfloor k / 2\rfloor}+k, \quad \text { for all integers } k \geq 2\) .

Use strong mathematical induction to show that \(c_{n} \leq n^{2}\) for all integers \(n \geq 1\).

Text Transcription:

c_1, c_2, c_3, ldots

c_1=0

c_k=2 c_lfloor k / 2 rfloor+k, for all integers k geq 2

c_n leq n^2

n geq 1