Ayuda a la prueba de suelo de inducción recursiva

Question

He intentado averiguar esto pero no sé cómo abordar el proceso inductivo,

Así que tengo números definidos recursivamente como sigue:

Para $C_1=0$ y para $n>1$

$$C_n=4C_{\lfloor n/2 \rfloor}+n$$

Dónde $\lfloor n/2 \rfloor$ es la función suelo.

Después de esa definición, tengo que demostrar que

$$C_n \le4(n-1)^2 \ \forall n \in \mathbb N$$

Ya probé para la base $C_1$ pero no sé cómo enfocarlo a partir de ahí. ¡Gracias cualquier ayuda! (:

Answer 1

Nota: Este problema requiere una inducción fuerte en lugar de sólo una inducción débil. En la inducción débil, la hipótesis es que el enunciado es válido para el valor anterior. Pero en la inducción fuerte, la hipótesis es que la afirmación es válida para todo valores precedentes que siguen siendo posteriores al caso base.

Por hipótesis de inducción se supone que $C_n\le 4(n-1)^2$ para todos $n<k$ . Entonces

\begin {align*} C_k&=4C_{ \lfloor k/2 \rfloor }+k \\ & \le 4( \lfloor k/2 \rfloor -1)^2+k \\ & \le 4 \left ( \frac {k}{2}-1 \right )^2+k \\ &=k^2-4k+4+k \\ &=k^2-3k+4 \\ & \le 4(k-1)^2 \end {align*}

para todos $k\ge 2$ . Para mostrar el último paso, considere la diferencia $$4(k-1)^2-(k^2-3k+4)=k(3k-5)$$

que es claramente positivo para todos $k\ge 2$