Let be the following language $L_k=\{w,|w| \mbox{ is divisible by } $k$\}$
How to prove that an automata that recognizes $L_k$ has at least $k$ states?
I tried to prove it by induction :
We are going to prove that an automata that recognizes $L_k$ has at least $k$ states.
Initialization for $k=1$:
We surely need at least one state to recognize that the length of a word $w$ is severable by $1$. $(P_1)$
Let's assume that an automata that recognizes $L_k$ has at least $k$ states. $(P_k)$ for a given and fixed $k$. We are going to show that this is still true for $k+1$.
if $|w|=k+1$ ... I haven't found an idea to generalize this demonstration, do you have any tip or idea to prove that an automata that recognizes $L_k$ has at least $k$ states?
Induction doesn't work well for automata; the state requirements for one language do not necessarily relate to the requirements for another language, even in situations like this.
I would mimic the Myhill-Nerode minimization process here. I.e, I would argue that each state represents an equivalence class of all strings that 'end at' that state [i.e if you run the DFA on that string as input, the transition on the last character puts you in that state]. Then I would observe that two strings whose lengths are not congruent mod $k$ cannot be equivalent; since there are $k$ possible congruence classes [think 'remainders], there must be at lease $k$ states. I invite you to fill in the details.