From Sipser's book:
Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $h$ be a state of $M$ called its "home". A synchronizing sequence for $M$ and $h$ is a string $s\in \Sigma^*$ where $\delta (q,s)=h$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).
Say that $M$ is synchronizable if it has a synchronizing sequence for some state $h$.
Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$. Moreover, can you improve upon this bound?
I am focused on proving the $k^3$ bound.
Preliminary findings: The DFA M, given that it is synchronizable, cannot have more than one absorbing state and if it indeed has one, the "home" state cannot be anything other than that absorbing state. But how do I go about proving the $k^3$ bound? My gut feeling tells me to use induction, yet I cannot find a recursive structure. This problem was also posted in the CS forum some time ago, but I did not gain further insight from that discussion.
Notation. Let $|S|$ denote the number of elements of a finite set $S$. Let $Q$ be the set of states of the automaton. Given $S \subseteq Q$ and $u$ a word, let $Su = \{ q\cdot u \mid q \in S \}$.
Hint. Let $S \subseteq Q$ with $|S| \geqslant 2$. Show that there exists a word $u$ of length $\leqslant k^2$ such that $|Su| < |S|$.