c. Sea k un entero con k 3. Cualquier cadena de longitud k que no contiene el eslabón patrón 111 empieza con un 0 o con un 1. Si inicia con un 0, ...

c. Sea k un entero con k 3. Cualquier cadena de longitud k que no contiene el eslabón patrón 111 empieza con un 0 o con un 1. Si inicia con un 0, esto puede ser seguido por cualquier cadena de k 1 eslabones que no contienen el patrón 111. Hay dk฀1 de éstas. Si la cadena empieza con un 1, entonces los primeros dos eslabones son 10 o 11. Si los primeros dos eslabones son 10, entonces pueden ser seguidos por cualquier cadena de los k 2 eslabones que no contienen el patrón 111. Existen dk฀2 de éstos. Si la cadena inicia con un 11, entonces el tercer eslabón debe ser 0 (porque la cuerda no contiene 111) y esos tres eslabones pueden ser seguidos por cualquier cadena de k 3 eslabones que no contienen el patrón 111. Hay dk฀3 de éstas. Por tanto, para todos los enteros k 3, dk dk฀1 dk฀2 dk฀3.